백준 1328번: 고층 빌딩 [C++]

작성일 | In
플래티넘 V 플래티넘 V

문제

고층 빌딩

풀이

총 $i$개의 빌딩을 왼쪽에서 봤을 때 $j$개, 오른쪽에서 봤을 때 $k$가 되도록 하는 빌딩의 배치의 수를 $DP[i][j][k]$라 합시다. 이때 빌딩은 높이가 $1$인 것부터 $i$인 것까지 있습니다.

이제 각 빌딩의 높이를 $1$씩 높여줍니다. 그러면 높이가 $2$인 것부터 $i + 1$인 것까지 있습니다. 여기에 높이가 $1$인 빌딩을 놓아주면 빌딩이 $i + 1$개일때의 경우도 계산할 수 있습니다.

점화식은 아래와 같습니다.

\[DP[i][j][k] = DP[i - 1][j - 1][k] + DP[i - 1][j][k - 1] + (i - 2)DP[i - 1][j][k]\]

$DP[i - 1][j - 1][k]$는 맨 왼쪽에 높이가 $1$인 빌딩을 놓는 경우, $DP[i - 1][j][k - 1]$은 오른쪽에 놓는 경우, $(i - 2)DP[i - 1][j][k]$는 빌딩 사이에 놓는 경우입니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll MOD = 1e9 + 7;

ll dp[101][101][101];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, L, R;
    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][j][k] += dp[i - 1][j][k - 1];
                dp[i][j][k] %= MOD;

                dp[i][j][k] += dp[i - 1][j][k] * (i - 2) % MOD;
                dp[i][j][k] %= MOD;
            }
        }
    }

    cout << dp[N][L][R];

    return 0;
}

백준 1328번: 고층 빌딩 [C++]