백준 - 1328번 고층 빌딩

문제

빌딩의 개수, 왼쪽에서 봤을 때 보이는 빌딩의 수, 오른쪽에서 봤을 때 보이는 빌딩의 수가
주어질 때 가능한 빌딩의 경우의 수 출력

(어떤 빌딩 뒤에 더 작은 높이의 빌딩이 있다면 가려져서 안 보임)

생각

빌딩이 1개일때, 2개일때, ,,, 빌딩 수를 점점 늘려가며 가능한 경우의 수를 저장하자!

빌딩 n - 1개를 사용해서 만들 수 있는 경우의 수를 알면
빌딩 1개를 추가했을 때, 즉 n + 1개의 빌딩을 사용했을 때 만들 수 있는 경우의 수를 알 수 있다!

긴 빌딩들 부터 사용해 점점 작은 빌딩을 넣어준다고 생각하거나,
빌딩을 끼워넣을 때 다른 길이들은 + 1씩 해주고, 길이 1인 빌딩을 넣는다고 생각하면,

1. 맨 왼쪽, 맨 오른쪽 각각 지금까지의 빌딩들보다 작은 길이의 빌딩 1개를 붙일 때
   붙인 쪽 옆에서 봤을 보이는 빌딩 수 + 1 가 되고,

2. 끝 위치가 아닌 빌딩들 사이사이에 지금까지의 빌딩들보다 작은 길이의 빌딩 1개를 끼워넣을 때
   기존 왼쪽, 오른쪽에서 보이는 빌딩 수는 변함 없이 빌딩 1개를 끼워넣을 수 있으므로,

s[사용한 빌딩의 수][왼쪽에서 보이는 빌딩의 수][오른쪽에서 보이는 빌딩의 수]
로 정하면 점화식은 다음과 같다

s[i][j][k] = s[i - 1][j][k] * (i - 2) + s[i - 1][j][k - 1] + s[i - 1][j - 1][k]

i개 빌딩을 사용해서 왼쪽에서 j개 오른쪽에서 k개가 보이는 경우의 수는
= 2번 경우 * 사이 사이 끼워넣을 수 있는 공간 수 + 1번 경우의 오른쪽 + 1번 경우의 왼쪽

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int n, l, r;
int s[105][105][105];

int main() {
	cin >> n >> l >> r;

	s[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++) {
				s[i][j][k] = ((long long)s[i - 1][j][k] * (i - 2) + s[i - 1][j][k - 1] + s[i - 1][j - 1][k]) % 1000000007;
			}
		}
	}

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

	return 0;
}