[BOJ 1328] 고층빌딩

문제

BOJ 1328 고층빌딩

유형

• DP

풀이

이전 경우의 수에서 높이가 1인 건물을 하나 추가한다고 생각하면 점화식을 찾을 수 있다.
일단 테이블은 dp[i][j][k] 건물이 i개일 때 왼쪽에서 j개 오른쪽에서 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] = dp[i-1][j][k] * (i - 2)가 된다.

먼저 첫번째 식의 의미는 건물이 i일때 왼쪽 j, 오른쪽 k개가 보이려면 건물이 i-1개일 때 왼쪽 j-1, 오른쪽 k개가 더해져야한다.
그리고 두번째는 위와 똑같이 i-1개의 건물에서 왼쪽 j, 오른쪽 k-1개 일 때를 더해주고
마지막으로 건물과 건물 사이의 개수를 i-2개이므로 i-1개의 건물일에서 왼쪽 j, 오른쪽 k개에 i-2를 곱한 값을 더해준다.

최종 점화식은
dp[i][j][k] = dp[i-1][j-1][k] + dp[i-1][j][k-1] + dp[i-1][j][k]*(i-2)

초기값은 dp[1][1][1] = 1로 설정해준다.

코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, l, r;
long long dp[101][101][101];

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);

	cin >> n >> l >> r;

	dp[1][1][1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int L = 1; L <= l; L++) {
			for (int R = 1; R <= r; R++) {
				dp[i][L][R] = (dp[i - 1][L - 1][R] + dp[i - 1][L][R - 1] + dp[i - 1][L][R] * (i - 2)) % 1000000007;
			}
		}
	}

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

	return 0;
}