백준 15988번: 1, 2, 3 더하기 3 (C++)

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

15988번: 1, 2, 3 더하기 3

---

Solved By: DP

 

4부터 다음과 같은 특징을 발견할 수 있었습니다.

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

1 + 3

2 + 1 + 1

2 + 2

3 + 1

로 4를 표현할 수 있는데 이 중에

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

1 + 3

는 앞에 1을 때고 보면 3을 만드는 방법과 같습니다.

2 + 1 + 1

2 + 2

또한 2를 만드는 방법과 같고,

3 + 1

마지막 또한 1을 만드는 방법과 같습니다.

 

사용하는 수가 1, 2, 3이 전부이기 때문에 N이 주어지면 각 N - 1, N - 2, N - 3을 만드는 방법들을 더해주면 답을 구할 수 있습니다. 

 

Top-Down DP로 구현했으며 나머지 정리 특성을 활용해 코드를 작성했습니다.

#include <iostream>
#define MAX 1000001
#define MOD 1000000009
using namespace std;

int T;
int cache[MAX];

int solve(int n){
    if(cache[n]) return cache[n];
    else return cache[n] = ((solve(n - 3) % MOD + solve(n - 2) % MOD) % MOD + solve(n - 1) % MOD) % MOD;
}

int main(){
    cache[1] = 1; cache[2] = 2; cache[3] = 4;
    cin >> T;
    for(int i = 0; i < T; i++){
        int n; cin >> n;
        cout << solve(n) << '\n';
    }
    
    return 0;
}