[백준] 15988번 : 1, 2, 3 더하기 3

문제

 

---

풀이

 

myunji.tistory.com/298

[백준] 9095번 : 1, 2, 3 더하기

이 문제를 풀 때는 n이 11보다 작기 때문에 재귀함수로 풀 수 있었다.

 

하지만 이번엔 n이 1,000,000까지 들어올 수 있기 때문에 재귀함수로 풀면 시간이 너무 오래 걸릴 것이다.

그래서 동적계획법(dp)로 풀어야 한다.

 

특정 수 i에 대해 i를 1, 2, 3의 합으로 나타내는 방법은 다음과 같다.

(i-1을 1, 2, 3의 합으로 나타낸 수열) + 1

(i-2를 1, 2, 3의 합으로 나타낸 수열) + 2

(i-3을 1, 2, 3의 합으로 나타낸 수열) + 3

 

이걸 점화식으로 표현하면 i가 4보다 크거나 같을 때,

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

라고 할 수 있다.

---

소스코드

 

#include <iostream>

using namespace std;

const int DIVISOR = 1000000009;
long long dp[1000001];

void dpSum() { //dp[i-1]+1, dp[i-2]+2, dp[i-3]+3
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    for (int i = 4; i <= 1000000; i++)
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % DIVISOR;
}

int main() {
    int T, n;

    dpSum();
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> n;
        cout<<dp[n]<<'\n';
    }
}

테스트 케이스마다 dp 연산을 하면 오래 걸릴 것 같아서 그냥 처음에 1,000,000까지의 dp 연산을 했다.