[BOJ] 1328 : 고층 빌딩

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

1328번: 고층 빌딩

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Platinum V

 

문제

상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다.

상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다.

빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어졌을 때, 가능한 빌딩 순서의 경우의 수를 구하는 프로그램을 작성하시오.

예를 들어, N = 5, L = 3, R = 2인 경우에 가능한 빌딩의 배치 중 하나는 1 3 5 2 4이다.

입력

첫째 줄에 빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어진다.

출력

첫째 줄에 가능한 빌딩 순서의 경우의 수를 1000000007로 나눈 나머지를 출력한다.

제한

• 1 ≤ N ≤ 100
• 1 ≤ L, R ≤ N

 

풀이

[n+1] * [L+1] * [R+1]크기의 dp배열을 만든다. dp[i][j][k]는 i개의 빌딩 중 왼쪽에서는 j, 오른쪽에서는 k개가 보이는경우의 수를 담는다.

1개의 빌딩이 있고, 왼쪽에서 1개, 오른쪽에서 1개 보이는 경우는 1개이므로 dp[1][1][1]은 1이다.

 

n = 5, l = 3, r = 2라고 했을 때, 총 n의 개수가 1이 늘어나서 n = 6, l = 3, r = 2라고 해보자.

이 때 기존의 빌딩들의 높이를 1 높이고, 높이가 1짜리인 빌딩을 추가한다고 생각하면 편하다.

n=5, l = 3, r=2에서 맨 오른쪽과 맨 왼쪽에만 두지 않으면 어느 경우에서든 n=6, l = 3, r = 2가 나올 것이다.

그러므로, (n이 하나 적을 때의 경우의 수) * (현재 n의 개수-2)

n = 6, l = 3, r = 2를 만들기 위해, n = 5, l = 2, r = 2에서 추가하는 경우도 있을 것이다. 이 경우는 맨 왼쪽에 1짜리 건물을 추가하면 

n = 5, l = 2, r = 2에서 n = 6, l = 3, r = 2가 된다.

그 반대 역시 성립한다. n = 6, l = 3, r = 2를 만들기 위해, n = 5, l = 3, r = 1에서 추가하는 경우도 있을 것이다.

이 경우는 맨 오른쪽에 1짜리 건물을 추가하면

n = 5, l = 3, r = 1에서 n = 6, l = 3, r = 2가 된다.

그 반대 역시 성립한다.

 

그러므로, 점화식을 아래와 같이 세울 수 있다:

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

이를 3차원 중첩 반복문을 돌려서(i는 2 -> n, j는 1 -> l, k는 1 -> r까지)

dp[n][l][r]이 n개의 빌딩에서 왼쪽에서 l개가 보이고, 오른쪽에서 r개가 보이는 경우의 수가 저장되므로, 이걸 출력하면 된다.

 

이 때, 값이 정수 범위를 넘을 수 있으니, 1e9+7로 잘 나눠주고, i-2를 곱할 때 범위를 이미 벗어날 수 있으므로, 잠깐 long long에 담아주도록 하자.

 

 

코드(C++)

 

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

int main(void)
{
    int n, l, r;
    cin >> n >> l >> r;

    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(l + 1, vector<int>(r + 1, 0)));

    dp[1][1][1] = 1;

    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= l; j++)
        {
            for (int k = 1; k <= r; k++)
            {
                dp[i][j][k] = ((long long)dp[i - 1][j][k] * (i - 2) + dp[i - 1][j][k - 1] + dp[i - 1][j - 1][k]) % MOD;
            }
        }
    }

    cout << dp[n][l][r];

    return 0;
}