BOJ 4811 알약

사용한 알고리즘

알고리즘 설명

이 문제는 알약의 갯수를 state를 하는 DP 문제이다
2차원으로 DP를 구성하자
DP(한개짜리 알약수)(반개짜리 알약수) 로 구성
각 상태에서 먹는 경우의 수가 DP의 값이다
점화식은 아래와 같다
- DP(x)(y) = DP(x-1)(y+1) + DP(x)(y-1)
- 단 위 식에서 x 또는 y 값이 음수라면 0이다.
- 또한 DP(0)(0)=1 이다

풀이

// baekjoon 4811 yechan
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAX_N=31;

int N;
ll dp[MAX_N][MAX_N];

ll dfs(int lt, int rt) {
    ll &ret = dp[lt][rt];
    if (ret != -1) return ret;

    ret = 0;
    // divide one, and eat
    if (lt > 0) ret += dfs(lt-1, rt+1);

    // just eat
    if (rt > 0) ret += dfs(lt, rt-1);

    return ret;
}

int main() {
    for (int i=0; i<MAX_N; i++)
        fill(dp[i], dp[i]+MAX_N, -1);
    dp[0][0]=1;
    while (1) {
        scanf("%d", &N);
        if (N == 0) break;
        printf("%lld\n", dfs(N,0));
    }
    return 0;
}