크리스마스 트리 꾸미기( BOJ 16468 )

16468. 크리스마스 트리 꾸미기 : https://www.acmicpc.net/problem/16468

16468번: 크리스마스 트리 꾸미기

 

문제 파악하기

• N개의 볼을 사용해 L 높이의 트리를 만드는 방법의 수를 구해야 합니다.
• 트리는 이진 트리 모양으로 구성되기에 N개의 볼이 있다면 (N-1)개의 볼을 왼쪽/오른쪽 자식으로 나눌 수 있습니다.
• (왼쪽 자식 수, 오른쪽 자식 수) 라고 표현한다면 N개의 볼은 (0, N-1) ~ (N-1, 0) 까지 총 (N-1)가지 경우의 수로 나눌 수 있습니다.
• 이렇게 나눈 다음, L의 높이를 만들 수 있는지 확인하면 됩니다. 다만, 정확히 L 높이를 만들 수 있는지 여부가 중요합니다.

 

문제 해결하기

• 트리는 왼쪽/오른쪽 중 한 곳이라도 L 높이를 가져야 합니다.
• 따라서, L 높이를 가지는 지 확인하는 DP 배열을 다음과 같이 만들 수 있습니다.
  >> DP[ball][height][0] : ball개의 볼을 가지고 height 이하의 높이를 가진 트리를 만드는 방법의 수
        DP[ball][height][1] : ball개의 볼을 가지고 정확히 height 높이를 가진 트리를 만드는 방법의 수
• 이렇게 DP 배열을 만들면, 2가지 경우(DP[ball][height][0]/DP[ball][height][1])에 대해 다르게 구할 수 있습니다.
• DP[ball][height][0]의 경우, 자식으로 나올 수 있는 모든 경우 중 height 이하의 높이를 가진 방법 수만 구하면 됩니다.
  DP[ball][height][1]의 경우, 왼쪽/오른쪽 자식 중 한 곳 이상이 height 높이를 가진 방법 수를 모두 구하면 됩니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#define NMAX 305
#define MOD 100030001
 
int N, L;
 
int dp[NMAX][NMAX][2];
 
int sv(int ball, int height, int f) {
 
    if(dp[ball][height][f] >= 0) return dp[ball][height][f];
 
    int minHeight, tmp;
    for(minHeight=0,tmp=ball ; tmp > 0 ; tmp/=2,minHeight++);
 
    // ball을 배치할 수 없는 경우
    if(height < minHeight) return dp[ball][height][f] = 0;
 
    // height 높이를 만들지 못하는 경우
    else if(ball < height) {
        if(f == 1) return dp[ball][height][f] = 0;
        else return dp[ball][height][f] = sv(ball, height-1, f);
    }
 
    // 종료 조건
    else if(ball == 0 and height == 0) return dp[ball][height][f] = 1;
 
    else {
        long long int ret=0;
 
        for(int nxt=0;nxt<ball;nxt++) {
            if(f == 0) ret = ( ret + 1LL*sv(nxt, height-1, 0)*sv((ball-1)-nxt, height-1, 0) )%MOD;
            else {
                ret = ( ret + 1LL*sv(nxt, height-1, 1)*sv((ball-1)-nxt, height-1, 0) )%MOD;
                ret = ( ret + 1LL*sv(nxt, height-1, 0)*sv((ball-1)-nxt, height-1, 1) )%MOD;
 
                // 중복 계산된 부분 제거
                ret = ( ret - 1LL*sv(nxt, height-1, 1)*sv((ball-1)-nxt, height-1, 1) + MOD)%MOD;
            }
        }
 
        return dp[ball][height][f] = ret;
    }
 
}
 
int main() {
    scanf("%d %d", &N, &L);
 
    memset(dp, -1, sizeof(dp));
    printf("%lld", sv(N, L, 1));
 
}

 

후기

3차원 배열을 활용한 점화식을 떠올리기 쉽지 않은 문제입니다. 볼의 개수와 높이의 상관 관계 또한 세심하게 구분해야 하기에 쉽지 않은 문제라고 생각합니다. 트리를 활용한 다이나믹 프로그래밍 보다는 전형적인 다이나믹 프로그래밍에 가까운 문제라고 생각합니다.