[python] 백준 1328 고층 빌딩

https://www.acmicpc.net/problem/1328

1328번: 고층 빌딩

 

문제 해결

• dp를 써야겠다라는 생각이 드는데 어떻게 써야할지 고민이 되는 문제
• n이 1이상 100이하이기 때문에 삼 중 반복문을 써도 괜찮다.
• dp[i][j][k]를 i개의 빌딩이 있을 때 왼쪽에서 보면 j개 오른쪽에서는 k개 보이는 배열가지수라고 하자.
• 그러면 dp[1][1][1] =1 이 된다. 가장 기본 값
• i-1개의 빌딩이 배열되어있다고 하자. 이제 빌딩 하나를 더 세워 dp[i][j][k]를 구하려고 한다.
• 이 때 dp[i][j][k] = dp[i-1][j-1][k] (맨 왼쪽 건물보다 작은 건물을 왼쪽에 세웠을 때) + dp[i-1][j][k-1](맨 오른쪽 건물보다 작은 건물을 오른쪽에 세웠을 때) + dp[i-1][j][k]*(i-2) (건물과 건물사이 조그만하게 세워 왼쪽 오른쪽 모두 보이지 않게 세우는 가지수)가 된다.
• 그림을 그려보는 것이 가장 쉽다!

 

CODE

mod =  1000000007
n, l , r = map(int, input().split())
dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
dp[1][1][1] = 1
for i in range(2,n+1):
    for j in range(1,l+1):
        for k in range(1,r+1):
            dp[i][j][k] = ((dp[i-1][j-1][k]+dp[i-1][j][k-1]+dp[i-1][j][k]*(i-2))%mod)
print(dp[n][l][r])