[1328] 고층 빌딩

https://www.acmicpc.net/problem/1328

1328번: 고층 빌딩

<문제>

아이디어를 잘 떠올리면 쉽게 풀 수 있다. 아이디어를 못떠올리면 한없이 어려워지는 문제였다.

 

기본 아이디어는 다음과 같다.

1) N개의 턴을 반복하고, 매턴이 시작하면 이미 지어진 건물의 높이를 1 증가시킨다.

2) 높이 1의 건물을 배치한다. 배치가 끝나면 턴이 종료된다.

 

2)를 진행할때에, 경우의수는 아래의 3가지로 나뉜다.

1. 맨 왼쪽에 배치하는 경우 -> 왼쪽에서 볼때의 건물의 개수가 1증가한다.

2. 맨 오른쪽에 배치하는 경우 -> 오른쪽에서 볼때의 건물의 개수가 1 증가한다.

3. 맨 왼쪽도, 맨 오른쪽도 아닌 그 사이 어딘가에 배치하는 경우 -> 갱신없음

 

<소스코드>

#include<stdio.h>
const int m = 1000000007;
long long dp[101][101][101];
int main(void) {
    int i, j, k, n, l, r;
    dp[1][1][1] = 1;
    scanf("%d %d %d", &n, &l, &r);
    for (i = 2; i <= n; i++) {
        for (j = 1; j <= l; j++) {
            for (k = 1; k <= r; k++) {
                dp[i][j][k] = dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + dp[i - 1][j][k] * (i - 2);
                dp[i][j][k] %= m;
            }
        }
    }
    printf("%lld", dp[n][l][r] % m);
    return 0;
}