고층 빌딩

---

DP풀이

1. n-1개의 건물에서 1개가 추가 되면 n개 건물이 된다.
2. dp[n]과 dp[n-1]사이의 관계식을 어떻게하면 도출해 낼수 있을까?
3. 1개의 건물이 추가될때, L과 R이 바뀌는 경우가 있고 바뀌지 않는 경우가 있다.
4. 바뀌는경우는 크게 두가지, dp[i][l][r] = dp[i-1][l-1][r] + dp[i-1][l][r-1] 이다.
5. 바뀌지 않는경우는 건물 사이에 있는경우, i-1개 건물사이에 i-2개의 경우의수 이므로, dp[i][l][r] = dp[i-1][l][r]*(i-2)이다.

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

---

실제 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <set>

using namespace std;
#define endl "\n"

#define Modular 1000000007
#define MAX 100+1
int N, L, R;
long long int dp[MAX][MAX][MAX];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> N>>L>>R;

	dp[1][1][1] = 1;
	for (int i = 2; i <= N; i++)
	{
		for (int l = 1; l <= i; l++)
		{
			for (int r = 1; r <= i; r++)
			{
				dp[i][l][r] = dp[i - 1][l - 1][r] + dp[i - 1][l][r - 1] + (dp[i - 1][l][r]*(i-2));
				dp[i][l][r] %= Modular;
			}
		}
	}

	cout << dp[N][L][R];
}

참고

https://thekeykim.github.io/posts/BOJ_1328/