[알고리즘 문제] 16468번 크리스마스 트리 꾸미기

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

 

1. 문제 분석 및 풀이

이전 포스팅에서 트리 dp에 대해 다뤘는데 대부분의 아이디어가 해당 노드를 루트로 하는 부분 트리에 대한 dt를 설정하여 진행하는 방법이었다. 이 문제도 너무 뻔히 tree dp임을 보이고 그냥 쉽게 만들면 된다고 생각했지만 단 한 가지 간과한 사실이 있었다.

 

dt[n][h] : 높이 h인 트리를 n개의 공을 이용해 만드는 가지 수

 

이렇게 정의하면 되는 것인가? 나는 처음에 된다고 생각했는데... 문제를 쫌 더 보니깐 트리가 정확히 높이가 H개 돼야 하야 한다는 사실을 잊고 있었다. 위의 dt는 사실 최대 높이가 h이지 실제 높이는 h이하인 트리를 만드는 가지 수이다. 

 

처음에 이 사실을 알고 당황했지만 13250번 주사위 게임 문제를 직전에 푼 경험을 떠올리며 dt를 ~이상인 경우로 설정하면 그냥 N이상 - (N-1) 이상의 경우를 구해주면 되는 것이다.  이 문제를 한 번쯤 풀어보는 것이 도움이 될 것이다. 

13250번: 주사위 게임

 

그리고 한 가지 더 실수할 수 있는 부분이 있는데 뺀 값의 모드가 음수일 수 있으므로 MOD값을 더한 후 MOD연산을 해주면 양수가 나온다. 나도 이 실수로 인해 5분 정도 더 고민한 것 같다.

 

 

2. 코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
long long int dt[305][305];
bool chk[305][305];
#define MOD 100030001

long long int process(int n, int h)
{
    if(dt[n][h] || chk[n][h]) return dt[n][h];
    chk[n][h] = 1;
    if(n>0&&h<=0) return 0;
    long long int sum = 0;

    int s = 0, e = n-1;
    while(s < e){
            long long int left = process(s++, h-1)%MOD;
            long long int right =  process(e--, h-1)%MOD;
            sum += (left*right*2)%MOD;
            sum %= MOD;
    }if(s==e) sum += (long long int)process(s,h-1) * process(e,h-1);
    return dt[n][h] = sum%MOD;
}

int main()
{
    for(int i=0; i<=300; i++) dt[0][i] = 1;
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    process(N, M);
    process(N, M-1);

    cout << (dt[N][M]-dt[N][M-1]+MOD)%MOD;
}

 

 

3. 소감 

사실 내가 가장 못하는 것은 수학에서 확률이나 경우의 수를 구하는 것인데... 이 문제를 풀면서 비슷한 느낌이 들었다. 경우의 수를 구할 때 이거면 해당 조건에 만족하는 경우만 보이겠지? 했는데... 이상한 것들 꼬이고 중복되고..

 

혹시 이런 경험을 해보신 분이나 해결 팁이 있다면 댓글 부탁드립니다. 물론 이런 문제를 많이 접해보면 쫌 괜찮아 지겠죠 ㅎㅎ?