BOJ 백준 8895번 막대 배치

 

BOJ 백준 8895 막대 배치

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

8895번: 막대 배치

​

높이가 1, 2, ... , n인 막대 n 개가 주어지고, 왼쪽에서 봤을 때 L 개, 오른쪽에서 봤을 때 R 개가 보이도록 막대를 배치하는 경우의 수를 구하는 것이 목표이다.

 

문제에서 높이가 1, 2, ... , n인 막대 n 개가 일렬로 배치되어 있다는 점에 주목했다. 막대가 n 개 있는데 굳이 높이가 1부터 n까지 한 개씩 있는 것은 일반적인 경우는 아니기 때문이다.

 

문제를 보고 다이나믹 프로그래밍(Dynamic programming)으로 풀어야 한다는 생각이 들었고, 이 문제에서는 가장 높은 높이 n인 막대부터 시작해서 내림차순으로 막대를 배치한다고 가정하는 것이 핵심 아이디어였다.

 

​

dp[n][l][r]: 막대를 n 개 배치한 상태에서 왼쪽에서는 l 개, 오른쪽에서는 r 개의 막대가 보이도록 하는 배치의 경우의 수

 

​

막대를 높이가 높은 것부터 낮은 것까지 차례대로 놓는다고 가정했으므로 막대를 하나씩 추가하는 이제까지 놓았던 막대들 중 가장 높이가 낮은 막대를 마지막에 추가하는 것이다. 그래서 추가하는 막대를 어느 위치에 놓느냐에 따라 왼쪽과 오른쪽에서 보이는 막대의 수가 달라질 수 있다. 여기서 추가하는 막대를 A라고 하면, 경우를 따져 봤을 때 다음과 같이 정리할 수 있다.

 

 

​

1) A를 가장 왼쪽에 놓는 경우

이전 단계보다 왼쪽 막대가 하나 더 보이게 되므로

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

 

 

2) A를 가장 오른쪽에 놓는 경우

이전 단계보다 오른쪽 막대가 하나 더 보이게 되므로

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

 

 

3) A를 가장 왼쪽 또는 오른쪽이 아니라 막대 사이에 놓는 경우

왼쪽과 오른쪽에서 보이는 막대 개수는 변함없으므로

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

여기서 곱하는 (n - 2)는 막대 사이에 놓을 수 있는 위치의 개수를 의미한다.

 

 

 

#include <cstdio>
#include <algorithm>
using namespace std;

const int N_MAX = 20;
const int L_MAX = 20;
const int R_MAX = 20;

int t, n, l, r;
long long dp[N_MAX + 1][L_MAX + 1][R_MAX + 1];

int main(){
    scanf("%d", &t);
    
    dp[1][1][1] = 1;
    for (int i = 2; i <= N_MAX; i++){
        for (int j = 1; j <= i; j++){
            for (int k = 1; k <= i; k++){
                dp[i][j][k] = dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + (i - 2) * dp[i - 1][j][k];
            }
        }
    }
    
    while(t--){
        scanf("%d %d %d", &n, &l, &r);
        printf("%lld\n", dp[n][l][r]);
    }
    
    return 0;
}