[C++/BOJ] 9095번 1, 2, 3 더하기

---

입력	출력
3 4 7 10	7 44 274

이 문제는 임의의 수 N이 입력으로 들어왔을 때,

이를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제입니다.

이는 잘 생각해보면 N을 시작으로 트리를 만들어 계산하면 됩니다.

 

이를 풀기 위해서 우리는 동적 계획법이라는 알고리즘을 사용합니다.

트리를 직접 그려 만들어 본다면 겹치는 부분이 계속 생깁니다.

//트리의 처음 가지는 N에서 N-1, N-2, N-3으로 나뉩니다.

이를 memo배열에 기억해 필요할 때마다 사용합니다.

그렇다면 코드로 봅시다. 

---

#include <iostream>
using namespace std;
int memo[12] = { 0, };

int solution(int num){
    if(num == 1 || num == 2){
        memo[num] = num;
        return memo[num];
    }
    if(num == 3){
        memo[num] = 4;
        return memo[num];
    }

    if(memo[num]){
        return memo[num];
    }

    return memo[num] = solution(num - 1) + solution(num - 2) + solution(num - 3);
}

int main(void){
    int n, data;
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> data;
        cout << solution(data) << "\n";
    }
    return 0;
}