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

1328번: 고층 빌딩

다이나믹 프로그래밍

 

1. 문제 해결 아이디어

일반적인 dp문제는 작은 부분 문제들을 해결하면서 큰 문제의 답을 찾는 느낌인데

이 문제는 조금 다른 느낌이다. (도저히 안 풀려서 힌트를 얻었다)

 

일단 dp배열은 dp[최대 높이][왼쪽에서 보이는 건물 수][오른쪽에서 보이는 건물 수] 이렇게 설정했다.

dp배열을 정해주는 건 어렵지 않았다. 

그리고 bottom up 방식으로 푸는 게 좋을 것 같다는 느낌이 크게 들었었다.

 

그런데 점화식을 도출하기가 정말 어려웠다.

나는 계속 가장 높은 건물의 높이를 움직여가며, 이전 답과 현재 답의 연관성을 찾으려고 했지만 실패했다.

 

힌트 : 높이가 1인 빌딩

---

N = 3일 때 나올 수 있는 빌딩의 배치는 총 6가지이다.(3!)

(1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,2,1)

 

여기서 모든 빌딩들의 높이를 1씩 더해주면 어떻게 될까

(2,3,4)(2,4,3)....

 

1씩 더해주어도 답은 그대로 인 것을 알 수 있다.

 

그래서 N = 4인 경우는 높이가 1인 빌딩을 끼워 넣는다고 생각하면 문제가 쉬워진다.!

• 높이가 1인 빌딩을 가장 왼쪽에 놓을 때 : 왼쪽에서 보이는 빌딩의 수가 1 늘어난다.
• 높이가 1인 빌딩을 가장 오른쪽에 놓을 때 : 오른쪽에서 보이는 빌딩의 수가 1 늘어난다.
• 높이가 1인 빌딩을 가장자리가 아닌 곳에 놓을 때 : 왼쪽, 오른쪽에서 보이는 빌딩의 수에 전혀 영향을 미치지 못한다.

빌딩을 가장자리가 아닌 곳에 놓는 경우의 수는 n-2 가 됨을 알 수 있다.

 

위 설명을 점화식으로 나타내면

dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1] + dp[n-1][l][r] * (n-2)

 

높이가 1인 빌딩을 사용하는 생각을 하는 게 정말 어려웠던 문제이다.

IQ 테스트 같기도 하다.. 

 

DP는 다른 알고리즘 유형보다 몇 배는 더 많은 시간이 필요한 유형이라고 생각된다. 

구현보다는 사고력을 요구하는 문제가 많은 것 같아서 정말 길게 보고 공부해야겠다.

---

2. 코드

bottom up 방식이다

매우 간단하다

#include <iostream>
 
#define MOD 1000000007
using namespace std;
 
int N, L, R;
long long dp[101][101][101];
 
void solve(){
    dp[1][1][1] = 1;
    
    for(int n = 2; n <= N; n++){
        for(int l = 1; l <= N; l++){
            for(int r = 1; r <= N; r++){
                dp[n][l][r] = (dp[n-1][l-1][r] + dp[n-1][l][r-1] + dp[n-1][l][r] * (n-2)) % MOD;
            }
        }
    }
    cout << dp[N][L][R];
}
 
int main(){
    cin >> N >> L >> R;
    solve();
    return 0;
}