백준 1328번 : 고층 빌딩 in Python
이 문제는 높이가 모두 다른 빌딩 N개가 한 줄로 세워져 있고, 이를 왼쪽 끝과 오른쪽 끝에 서서 봤을 때 보이는 빌딩 수를 알 때 가능한 빌딩 순서의 경우의 수를 구하는 문제이다.
이 문제는 단순히 순열과 조합만을 이용해 경우의 수를 구하기는 어렵다. 빌딩의 높이에 따라 가려지는 빌딩이 달라지고, 또한 가려지는 빌딩의 수 역시 고려해야 하기 때문이다. 그래서 다른 방법을 이용해 문제를 해결해야 한다. 어떤 방법으로 해결할 수 있을까?
N-1개의 빌딩이 한 줄로 세워져 있을 때 모든 L, R(1 <= L, R <= N-1)에 대해 위 문제의 답을 구했다고 가정해보자. 그러면 각 경우에 대해 높이가 1인 빌딩부터 높이가 N-1인 빌딩까지 한 줄로 세워져 있을 것이다. 이 상태에서 N개의 빌딩에 대한 문제의 답을 구하려고 한다면, 한 개의 빌딩만 추가하면 될 것이다. 여기에는 크게 두 가지 방법이 있다.
하나는 높이가 N인 빌딩을 추가하는 것이고, 다른 하나는 기존에 있던 빌딩의 높이를 1 증가시키고 높이가 1인 빌딩을 추가하는 것이다. 그러나 높이가 N인 빌딩을 추가하는 경우 이 빌딩으로 인해 다른 빌딩이 가려져 기존의 경우의 수를 활용하기가 어렵다. 그래서 후자의 방법이 더 적절하다.
높이가 1인 빌딩을 한 줄로 세워진 N-1개의 빌딩(높이가 2~N 사이)에 추가하는 경우는 크게 3가지로 나뉜다. 우선 두 빌딩 사이에 높이가 1인 빌딩을 세우는 경우 왼쪽이나 오른쪽에서 봤을 때 기존에 있던 빌딩이 높이가 2 이상이라 높이가 1인 빌딩을 가리기 때문에 왼쪽이나 오른쪽에서 보이는 빌딩의 수의 변화가 없다. 그리고 높이가 1인 빌딩이 왼쪽 끝(오른쪽 끝)에 위치하는 경우 왼쪽(오른쪽)에서 보이는 빌딩의 수가 1 증가한다. 이를 모두 종합하면 빌딩의 개수가 i개이고 왼쪽 끝과 오른쪽 끝에 보이는 빌딩의 수가 각각 j개, k개인 경우의 수를 dp[i][j][k]라 하면, 높이가 1인 빌딩이 i-1개의 빌딩 중 두 빌딩 사이에 있는 경우는 i-2가지이므로, dp[i][j][k] = (i-2)*dp[i-1][j][k] + dp[i-1][j-1][k](높이가 1인 빌딩을 왼쪽 끝에 두는 경우) + dp[i-1][j][k-1](높이가 1인 빌딩을 오른쪽 끝에 두는 경우)가 된다. 이 점화식과 초기값 dp[1][1][1] = 1을 이용해 모든 1 <= i <= N, 1 <= j <= L, 1 <= K <= R에 대해 계산하면 dp[N][L][R], 즉 우리가 원하는 결과를 얻을 수 있다.
이를 코드로 구현하면 다음과 같다.
N, L, R = map(int, input().split())
dp = [[[0]*(R+1) for _ in range(L+1)] for _ in range(N+1)]
dp[1][1][1] = 1
for i in range(1, N+1):
for j in range(1, min(L, i)+1):
for k in range(1, min(R, i)+1):
dp[i][j][k] = (i-2)*dp[i-1][j][k] + dp[i-1][j-1][k] + dp[i-1][j][k-1]
print(dp[N][L][R]%1000000007)