백준 1328 - 고층 빌딩

www.acmicpc.net/problem/1328

 

아이디어

빌딩을 큰 것부터 놓는다고 해보자. 그러면 그 다음 빌딩을 놓는 경우는 크게 세가지로 나눌 수 있다.

 

1. 가장 왼쪽에 배치

 

2. 가장 오른쪽에 배치

 

3. 가운데 아무데나 배치

 

왼쪽에 놓을 경우 그저 왼쪽에서 볼 수 있는 빌딩의 수가 하나 늘어나는 것이므로

 

빌딩을 n개 놓을 때 왼쪽에서 l개 보고 오른쪽에서 r개 보는 경우 = 빌딩을 n - 1개 놓을 때 왼쪽에서 l - 1개 보고 오른쪽에서 r개 보는 경우가 성립함을 알 수 있다.

 

오른쪽도 마찬가지다.

 

중간에 배치하는 경우는 배치할 빌딩이 가장 작으므로 왼쪽이나 오른쪽에서 볼 수 있는 빌딩의 개수는 변하지 않는다.

 

즉 빌딩을 n개 놓을 때 왼쪽에서 l개 보고 오른쪽에서 r개 보는 경우 = 빌딩을 n - 1개 놓을 때 왼쪽에서 l개 보고 오른쪽에서 r개 보는 경우 * 빌딩 사이에 놓는 경우가 성립한다.

 

구현

앞서 이야기 한 세가지를 통해 경우의 수를 높은 빌딩부터 배치하는 방식으로 점화식을 정할 수 있음을 알 수 있다.

 

dp[i][j][k] = dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + dp[i - 1][j][k] * (i - 2)

 

이 점화식을 구현하기만 하면 문제를 해결 할 수 있다.

 

전체 코드

#include <iostream>
 
using namespace std;
using ll = long long;
 
static int mod = 1e9 + 7;
int n, l, r;
 
ll dp[101][101][101];
 
int main()
{
    dp[1][1][1] = 1;
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> l >> r;
 
    for (int i = 2; i <= n; ++i)
    {
        for (int j = min(i, l); j > 0; --j)
        {
            for (int k = min(i, r); k > 0; --k)
            {
                dp[i][j][k] = dp[i - 1][j - 1][k];
                dp[i][j][k] += dp[i - 1][j][k - 1];
                dp[i][j][k] %= mod;
                dp[i][j][k] += dp[i - 1][j][k] * (i - 2);
                dp[i][j][k] %= mod;
            }
        }
    }
 
    cout << dp[n][l][r];
}