백준 1328 : 고층 빌딩 c++

코드

#include <iostream>

using namespace std;

long long dp[101][101][101];

int main(){		
	int N, L, R;
	cin >> N >> L >> R;
	
	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)) % 1000000007;
			}
		}
	}
	
	cout << dp[N][L][R] % 1000000007;
	
	
	return 0;
}

알게된 점

첫 플래티넘 문제라 고민을 많이 해봤는데 어려워서 풀이를 봤다.

간단한 풀이일줄은 알았는데 생각하는게 어려웠다.

건물의 순서를 수열로 보면

이런식으로 나열이 되어 있을것이다. 그런데 여기서

1을 던한다고 하더라도 왼쪽에서 본 건물의 수와, 오른쪽에서 본 건물의 수는 변하지 않는다.

이때의 건물높이의 최소값은 2가되고, 1인 건물을 추가한다고 생각하면 건물의 개수가 n개일때와, n+1일때의 관계를 파악해 점화식을 세울 수 있다.

 

1. 가장 왼쪽에 1인 건물을 놓는 경우

전체건물수가 1이 늘어나고, 왼쪽에서 바라봤을때, 건물수가 1이 늘어난다. 오른쪽에서 바라봤을때는 그대로이다.

 

2. 가장 오른쪽에 1인 건물을 놓는경우

전체건물수가 1이 늘어나고, 오른쪽에서 바라봤을때, 건물수가 1이 늘어난다. 왼쪽에서 바라봤을때는 그대로이다.

 

3. 1,2를 제외한 곳에 1인 건물을 놓는 경우

전체건물수가 1이 늘어나고, 오른쪽에서 바라봤을때, 왼쪽에서 바라봤을때는 그대로이다.

이 경우는 n-2가지의 경우를 가지고 있다.

 

그래서 dp를 dp[n][l][r]로 세우면 (n = 전체건물수, l = 왼쪽에서 바라봤을 때 건물 수, r = 오른쪽에서 바라봤을 때 건물수)

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

이를 dp로 풀게되면 풀리게 된다!