# 백준 : 1,2,3 더하기(9095)

문제

https://www.acmicpc.net/problem/9095

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_9095_add123)

int main(void) {
    // insert code here...
    int testcase;
    int num;
    int result[11];
    result[0] = 1;
    result[1] = 2;
    result[2] = 4;
    result[3] = 7;
    for(int i=4; i<11; i++) {
        result[i] = result[i-3] + result[i-2] + result[i-1];
    }
    vector<int> testcase_arr;
    cin>>testcase;
    for(int i=0; i<testcase; i++) {
        cin>>num;
        testcase_arr.push_back(num);
    }
    for(int i=0; i<testcase; i++) {
        cout<<result[testcase_arr[i]-1]<<endl;
    }
    return 0;
}

풀이

DP에 대해 계속 공부하는 중인데, 솔직히 말하면 DP 좀 어렵다.
큰 문제를 작게 나누어서 생각하면 된다고 하는데 이게 말이 쉽지...
이 문제 솔직히 풀고나서 너무 쉬웠는데, 생각하는 과정이 정말 쉽지 않았다.
DP? 그러면 당연히 나누어야겠고. 근데 이거 피보나치같이 규칙이있는데.. 이건 아닌거같고.
DP에 대해서 계속 부담을 갖고 있어서 그런가. (헛소리)

무튼. 풀이를 작성해보면, 간단하다. 
1은 1가지 방법으로, 
2는 2가지 방법(1+1)으로, 
3은 4가지 방법(1+1+1, 2+1, 1+2, 3)으로,
4는 문제에서 나와있다싶이 7가지 방법으로
그러니까 결국 N은 (N-3) + (N-2) + (N-1) 방법의 합으로 구할 수 있는 것이다.

끝.