[백준] 1328번: 고층 빌딩

1328번: 고층 빌딩

문제

상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다.

상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다.

빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어졌을 때, 가능한 빌딩 순서의 경우의 수를 구하는 프로그램을 작성하시오.

예를 들어, N = 5, L = 3, R = 2인 경우에 가능한 빌딩의 배치 중 하나는 1 3 5 2 4이다.

입력

첫째 줄에 빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어진다. (1 ≤ N ≤ 100, 1 ≤ L, R ≤ N)

출력

첫째 줄에 가능한 빌딩 순서의 경우의 수를 1000000007로 나눈 나머지를 출력한다.

예제 입력 1

3 2 2

예제 출력 1

2

 

작은 크기부터 생각해야 하고, 3차원 배열을 사용했다는 것을 캐치해야 합니다. 

n = 1, l = 1, r = 1일 때가 제일 작을 때이고, 여기서부터 n을 증가시켜가면서 생각해서 문제를 풀면 됩니다.

 

#include <iostream>
using namespace std;
#define MOD 1000000007;
long long building[101][101][101];

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

    building[1][1][1] = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= l; j++) {
            for (int k = 1; k <= r; k++) {
                long long tmp = building[i][j][k];
                if (j + 1 <= l) {
                    building[i + 1][j + 1][k] += tmp;
                    building[i + 1][j + 1][k] %= MOD;
                }
                if (k + 1 <= r) {
                    building[i + 1][j][k + 1] += tmp;
                    building[i + 1][j][k + 1] %= MOD;
                }
                building[i + 1][j][k] += tmp * (i - 1);
                building[i + 1][j][k] %= MOD;

            }
        }
    }

    cout << building[n][l][r] << '\n';

    return 0;
}