[BOJ 1328] 고층 빌딩

N개의 빌딩이 있고 L = A, R = B일 때, N - 1개을 이용해서 어떻게 어떻게 만들 수 있을까?

 

 

 

N - 1개의 빌딩들의 범위는 1 ~ N - 1이다. 각 높이에 1을 더해주고, 높이가 1짜리인 빌딩을 놓으면 N개의 빌딩을 만들 수 있다.

 

 

 

높이가 N인 빌딩을 이용했다면, 점화식을 세울 수 있을지 없을지도 모른다.

 

 

 

하지만, 높이가 1짜리인 빌딩을 이용하므로 점화식이 간편해진다.

 

 

 

해설코드(C++).

#include <iostream>
using namespace std;
 
int N, L, R;
long long dp[101][101][101];
 
int main() {
  cin >> N >> L >> R;
  dp[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++){
          dp[i][j][k] = ((dp[i - 1][j - 1][k] % 1000000007)
          + (dp[i - 1][j][k - 1] % 1000000007)
          + ((i - 2) * dp[i - 1][j][k] % 1000000007)) % 1000000007;
        }
      }
  }
 
  cout << dp[N][L][R] << endl;
  return 0;
}