[백준] 8895 막대 배치

문제 주소 : www.acmicpc.net/problem/8895

8895번: 막대 배치

문제 확인

 

DP 문제입니다.

n과 n-1의 관계를 생각해보면 쉽게 풀 수 있습니다.

n개의 막대에서 n 혹은 1 막대를 제거하면 n-1이 됩니다. n막대를 제거하면 1~n-1개의 막대를 나열하는 경우가 되며, 1 막대를 제거하면 2~n 막대를 나열하는 경우이며 모든 막대의 길이를 1 줄이게 되면 1~n-1 막대를 나열하는 경우와 같은 경우의 수를 가집니다.

이 특성을 이용해 n과 n-1의 관계를 이용하여 점화식을 세웁니다.

 

풀이

 

막대 1을 기준으로 생각하면 좀 더 쉽게 풀 수 있습니다.

막대 1이 왼쪽/오른쪽 끝에 위치할 때 막대 1이 사라지게 된다면 n값과 함께 l, r 값이 1 줄게 됩니다.

=> dp[n][l][r] += dp[n-1][l-1][r] + dp[n-1][l][r-1]

막대 1이 0과 n-1 위치 사이인 1~n-2 사이에 위치한 경우 n 값만 1이 줄게 되고 l, r에는 변동이 없습니다.

=> dp[n][l][r] += (n-2) * dp[n-1][l-1][r]

 

코드

#include <cstdio>
int main() {
    long long dp[20][20][20] = { 1 };
    for (int n = 1; n < 20; n++) 
        for (int l = 0; l < 20; l++)
            for (int r = 0; r < 20; r++) {
                dp[n][l][r] = (n - 1)*dp[n - 1][l][r];//사이
                if (l)
                    dp[n][l][r] += dp[n - 1][l - 1][r];//왼쪽 끝
                if (r)
                    dp[n][l][r] += dp[n - 1][l][r - 1];//오른쪽 끝
            }
                
    int t, n, l, r;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &l, &r);
        printf("%lld\n", dp[n - 1][l - 1][r - 1]);
    }
}