백준 1328번 : 고층 빌딩

  문제를 읽고 나서 '아! 역시 골드 1 문제구나'라는 생각이 들었다. 어렵다! 어려워! dp 문제인 것은 알겠는데 점화식이 도저히 상상이 안됐었다. 그래서 다른 분들의 블로그를 참고했다.

---

풀이

  문제를 쉽게 풀기 위한 기본으로 전제는 이렇다.

 

1. 아무것도 없는 상태에서 키가 큰 순서대로 빌딩을 배치한다. 총 빌딩의 갯수가 10개였다면 높이가 10인 빌딩을 먼저 배치한 후 높이가 9인 빌딩을 배치하고 높이가 8인 빌딩을 배치하고... 그런식이다. 2. 빌딩을 배치할 수 있는 경우는 3가지로 나눈다. 제일 왼쪽에 배치, 제일 오른쪽에 배치, 그 외의 위치에 배치 3. dp[n][l][r] 이란 n개의 빌딩을 배치해서 왼쪽에서 봤을 때 l개의 빌딩이 보이고 오른쪽에서 봤을 때 r개의 빌딩이 보일 수 있는 경우의 수다.

  이렇게 되면 dp[n][l][r]이 되는 경우의 수는 3가지가 존재한다.

 

  먼저 n-1개의 빌딩이 있는 상태에서 제일 왼쪽에 그 다음 빌딩을 배치하는 경우. 이때 추가되는 빌딩의 높이는 현존하는 빌딩 중 제일 작다.(전제 1번) 따라서 왼쪽에서 바라봤을 때 빌딩의 갯수를 1개 증가시키고 오른쪽에서 바라봤을 때는 그대로가 된다. 즉 dp[n-1][l-1][r]에서 진입한다.

 

  다음으로 n-1개의 빌딩이 있는 상태에서 제일 오른쪽에 그 다음 빌딩을 배치하는 경우. 이때는 반대로 왼쪽에서 바라봤을 때는 그대로 오른쪽에서 바라봤을 때는 보이는 빌딩의 갯수가 1개 증가한다. 즉 dp[n-1][l][r-1]에서 진입한다.

 

  마지막으로 제일 오른쪽도, 제일 왼쪽도 아닌 경우. n-1개의 빌딩이 존재하는 상황에서 양쪽 끝을 배제하면 n-2개의 위치에 배치할 수 있는데 추가되는 빌딩의 높이가 다른 모든 빌딩의 높이보다 작다보니까 왼쪽에서 봐도 오른쪽에서 봐도 보이는 빌딩의 갯수는 그대로다. 즉 dp[n-1][l][r]에서 진입한다.

 

  따라서 dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1] + (n-2)*dp[n-1][l][r]이다.

 

#include <iostream>

using namespace std;

int n, l, r;
long long dp[101][101][101];

int main()
{
    cin >> n >> l >> r;
    
    dp[1][1][1] = 1;
    
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            for(int k = 1; k <= i; k++)
            {
                dp[i][j][k] = (dp[i-1][j-1][k] + dp[i-1][j][k-1] + dp[i-1][j][k] * (i-2)) % 1000000007;
            }
        }
    }
    
    cout << dp[n][l][r];
    
    return 0;
}