BOJ4811.md

문제

알약

문제 원본

문제의 원본은 여기서 확인하세요.

분류

• 다이나믹 프로그래밍

풀이

완전한 알약이 없는 경우 0, 반개짜리 하나만 남은경우 1을 반환하고, 두가지 경우를 나눠서 생각한다.

1. 한개짜리를 먹고 반개짜리를 집어 넣는 경우
2. 반개짜리를 먹는 경우

먼저 첫번째 경우, solve(w-1, h+1)을 재귀 호출 하고 dp[w][h]에 저장 두번째 경우도 만족하는 경우, solve(w, h - 1) 을 재귀호출 하고 dp[w][h]에 가산

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

long long dp[31][31];

long long solve(int w, int h) {
    // 완전한 알약이 0 미만인 경우 0
    if (w < 0) {
        return 0;
    }

    // 반개짜리만 남은 경우
    if (w == 0 && h == 1) {
        return 1;
    }

    // 이미 연산한 값이 있다면 반환
    if (dp[w][h] != -1) {
        return dp[w][h];
    }

    // 없다면 연산
    // 한개짜리 먹고 반개짜리 집어 넣는경우
    dp[w][h] = solve(w - 1, h + 1);

    // 반개짜리를 먹는 경우도 더해준다.
    if (h >= 1) {
        dp[w][h] += solve(w, h - 1);
    }

    return dp[w][h];
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    while (true) {
        memset(dp, -1, sizeof(dp));

        int n;
        cin >> n;

        if (n == 0) {
            break;
        }

        cout << solve(n, 0) << endl;
    }


    return 0;
}