백준_9095_1, 2, 3 더하기

다이나믹 프로그래밍(dp) 문제였다. 단순한 분할 정복 기법만 사용하면, 답을 구하는 계산을 계속 반복해서 하게 되기 때문에 메모이제이션(답을 배열에 저장해두고 꺼내씀)을 사용하는 기법인 dp를 이용해 풀었다. 

#include <iostream>
#define MAX 11
using namespace std;

int d[MAX];

int solve(int n) {
    if(n==1)
     return 1;
    if(d[n]!=0)
     return d[n];
    if(n==2)
     return d[n]=solve(n-1)+1;
    if(n==3)
     return d[n]=solve(n-1)+solve(n-2)+1;
    else
     return d[n]=solve(n-1)+solve(n-2)+solve(n-3);
}

int main() {
    int x;
    cin>>x;
    for(int i=0;i<x;++i) {
        int n;
        cin>>n;
        cout<<solve(n)<<endl;
    }
    return 0;
}