[BaekJoon][1328] 고층 빌딩

 BAEKJOON ONLINE JUDGE

1328 고층 빌딩

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

DP

dp[n][l][r] -> n : 건물의 수     l : 왼쪽에서 봤을 때 빌딩의 수    r : 오른쪽에서 봤을 때 빌딩의 수

n - 1 건물의 수의 상태에서 건물을 추가하여 경우의 수를 구해나가는 과정

이때, 길이 n 번째 건물을 추가하여 경우의 수를 따지기보다 길이 1의 건물을 추가한다고 생각하면 점화식을 구하기 쉽다.

예를 들어, 3개의 건물 2, 3, 4가 존재 할 때

    l , r

234    3, 1

324    2, 1

243    2, 2

342    2, 2

423    1, 2

432    1, 3

이 경우에 길이 1인 건물을 추가해 보자

1. 맨 앞에 추가하기    -> l + 1이 된다.

       l , r

1 234    4, 1

1 324    3, 1

1 243    3, 2

1 342    3, 2

1 423    2, 2

1 432    2, 3

2. 맨 뒤에 추가하기    -> r + 1이 된다.

       l , r

234 1    3, 2

324 1    2, 2

243 1    2, 3

342 1    2, 3

423 1    1, 3

432 1    1, 4

3. 그 외 아무데나 추가하기    -> 변화 없음

      l , r                        l , r

2134    3, 1        2314    3, 1

3124    2, 1        3214    2, 1

3124    2, 1        3214    2, 1

3142    2, 2        3412    2, 2

4123    1, 2        4213    1, 2

4132    1, 3        4312    1, 3

따라서 점화식을 세우면

dp[n][l][r] = dp[n - 1][l][r] * (n - 2) + dp[n - 1][l - 1][r] + dp[n - 1][l][r + 1]이다.

또한 dp[n][1][n] = dp[n][n][1] = 1로 각각 오름차순과 내림차순으로 정렬되어 있을 경우 나올 수 있는 값이며 경우의 수 이다.

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