[백준/BOJ] 4811 알약

문제 : 4811 알약

4811번: 알약

매일매일 알약을 꺼내먹었을 때, 전체 조각과 반 조각을

뽑는 순서의 경우의 수를 세 출력하는 문제이다.

남은 알약이 모두 반 조각 짜리라면 문자열이 결정되고,

반 조각짜리 알약이 음수 개인 경우는 불가능하게 처리하여

memoization기법을 활용해 Top-Down 방식의 DP를 짜서

이전 결과 값을 저장해 꺼내서 출력했다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M, arr[35][35];
ll DP(ll now, ll x){
    if (now==0)
        return 1;
    else if (x<0)
        return 0;
    else if (arr[now][x]!=-1)
        return arr[now][x];
    else
        return arr[now][x]=DP(now-1,x+1)+DP(now,x-1);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    fill(&arr[0][0],&arr[34][35],-1);
    while (1){
        ll N;
        cin >> N;
        if (N==0)
            break;
        cout << DP(N,0) << "\n";
    }
    return 0;
}