[BOJ 8895] 막대 배치

 2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8895에서 채점할 수 있습니다.

요약 )

 문제는 높이가 1,2,...,n 인 n개의 막대를 일렬로 세울 때, 왼쪽에서 보이는 막대가 l개, 오른쪽에서 보이는 막대가 r개가 되는 경우의 수를 구하는 것입니다. 이 문제는 '문제'를 '하위 문제'들로 나누어 해결하는 동적계획법으로 해결할 수 있습니다.

DP 배열 구하기 )

 먼저 DP문제를 정의해야 합니다. 다행히 이 문제는 있는 그대로, 아래처럼 DP를 정의해도 해결할 수 있습니다.

  dp[n][l][r] = n개의 막대, 왼쪽에서 보이는 막대가 l개, 오른쪽에서 보이는 막대가 r개일 때의 답

 이제 하위 문제를 찾아야 합니다. 높이가 n인 막대의 위치를 기준으로 하위 문제를 설정하여도 문제를 해결할 수 있지만, 다소 복잡합니다. 따라서 이 풀이에서는 높이가 1인 막대의 위치를 기준으로 하위 문제를 설정하도록 하겠습니다.

하위 문제 1 ) 높이가 1인 막대의 위치가 제일 왼쪽인 경우

-> 높이가 1인 막대를 치웠다고 생각해 봅시다.

-> 왼쪽에서 보이는 개수만 한 개 줄어듭니다.

-> n-1개의 막대, 왼쪽에서 l-1개 보이고, 오른쪽에서 r개 보이는 상황과 동일합니다.

-> dp[n-1][l-1][r] 에 그 답이 저장되어 있습니다.

하위 문제 2 ) 높이가 1인 막대의 위치가 제일 오른쪽인 경우

-> 높이가 1인 막대를 치웠다고 생각해 봅시다.

-> 오른쪽에서 보이는 개수만 한 개 줄어듭니다.

-> n-1개의 막대, 왼쪽에서 l개 보이고, 오른쪽에서 r-1개 보이는 상황과 동일합니다.

-> dp[n-1][l][r-1] 에 그 답이 저장되어 있습니다.

하위 문제 3 ) 높이가 1인 막대의 위치가 2 ~ n-1 위치인 경우

-> 높이가 1인 막대를 치웠다고 생각해 봅시다.

-> 보이는 막대 개수는 변하지 않습니다.

-> n-1개의 막대, 왼쪽에서 l개 보이고, 오른쪽에서 r개 보이는 상황과 동일합니다.

-> dp[n-1][l][r] 에 그 답이 저장되어 있습니다.

 하위 문제 1, 2 는 1개의 위치, 3은 n-2개의 위치에서 가능하므로 아래와 같은 관계식이 성립합니다.

  dp[n][l][r] = (하위 문제 1) + (하위 문제 2) + (n-2) * (하위 문제 3)

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

// code by RiKang, weeklyps.com
 
long long dp[25][25][25]; // 정답 = dp[n][l][r]
 
void get_dp(){
    dp[1][1][1] = 1;
    for(int i=2; i<=20; 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];
            }
        }
    }
}

정답 구하기 )

 DP 배열이 구해진 상태에서는 dp[n][l][r]을 출력해주면 끝입니다.

// code by RiKang, weeklyps.com
 
void solve(){
    scanf("%d %d %d",&n,&l,&r);
    printf("%lld\n",dp[n][l][r]);
}

최종 코드 )

// code by RiKang, weeklyps.com
// 2012 ACM-ICPC Daejeon regional - H
// BOJ 8895 막대 배치
// O(n^3) solution
 
#include <bits/stdc++.h>
using namespace::std;
 
int n, l, r;
long long dp[25][25][25]; // 정답 = dp[n][l][r]
 
void get_dp(){
    dp[1][1][1] = 1;
    for(int i=2; i<=20; 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];
            }
        }
    }
}
 
void solve(){
    scanf("%d %d %d",&n,&l,&r);
    printf("%lld\n",dp[n][l][r]);
}
 
int main(){
    get_dp();
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}