BOJ 1328 - 고층 빌딩

www.acmicpc.net/problem/1328

1328번: 고층 빌딩

 

이 문제는 DP 를 이용해야 풀 수 있는 문제이다.

 

DP[i][j][k] = w : 지은 건물이 i 개 이며, 왼쪽에서 j 개의 건물이 보이고, 오른쪽에서 k 개의 건물이 보일때, 가능한 총 경우의 수가 w 이다. 

 

건물을 지을때, 가장 높이가 높은거 부터 가장 높이가 작은 1인 건물을 제일 마지막에 짓는다고 가정할때, 3개의 경우의 수가 생긴다

 

1) 가장 왼쪽에 건물을 짓는다. (DP[i - 1][j - 1][k])

: 건물의 크기가 1 이므로, 왼쪽에서 볼때만 수가 하나 증가한다. 

 

 

2) 가장 오른쪽에 건물을 짓는다 (DP[i - 1][j][k - 1])

: 마찬가지로 건물의 크기가 1이므로, 오른쪽에서 볼때만 갯수가 하나 증가한다.

 

 

3) 양 끝이 아닌 중간에 세울 때 (DP[i - 1][j][k] * (i  - 2))

: 중간에 놓을때는, 양 끝을 제외한 i - 2 개 의 경우의 수가 존재한다

 

 

- 참고 : octorbirth.tistory.com/254

[BOJ] 백준 1328 고층빌딩

 

DP 는 거의 혼자서 풀 수 있는 문제가 없는것 같다.

 

 

- c++

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 1e9+7;
int N, L, R;
// dp[i][j][k] = w : 건물이 i 개 이고, 왼쪽과 오른쪽에서 각각 j, k 개가 보이는 경우 가능한 총 경우의 수가 w. 
int dp[101][101][101];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> L >> R;
    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;
}