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

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

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

---

1, 2, 3 더하기 3 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다.

1을 만드는 경우의 수는 아래와 같습니다.

1

2를 만드는 경우의 수는 아래와 같습니다.

1 + 1
2

3를 만드는 경우의 수는 아래와 같습니다.

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
1 + 3

4를 만드는 경우의 수는 아래와 같습니다.

3 + 1

2 + 1 + 1
2 + 2

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
1 + 3

4를 만드는 경우의 수를 보면, 1을 만드는 경우의 수에 3을, 2를 만드는 경우의 수에 2를, 3을 만드는 경우의 수에 1을 더해주어 만들어짐을 알 수 있습니다.

 

따라서 테이블 d[i]는 아래와 같이 정의할 수 있습니다. (단, d[i]는 i를 1, 2, 3의 합으로 만드는 방법의 수 % 1000000009)

// d[i - 1], d[i - 2], d[i - 3]은 1000000009 보다 작으므로 MOD 연산을 수행하지 않아도 됨
d[i] = (d[i - 1] + d[i - 2] + d[i - 3]) % 1000000009;

 

단, 주의 할 점은 d[i]는 1000000009보다 작은 세 개의 수를 더하는 연산을 수행하므로 int형의 범위를 벗어날 수 있습니다.

따라서 d[i]는 long long형으로 정의해야합니다.

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000009
long long d[1000010];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t, n; cin >> t;

    d[1] = 1; d[2] = 2; d[3] = 4;   // 초기값
    for(int i = 4 ; i <= 1000000; i++)
        d[i] = (d[i - 1] + d[i - 2] + d[i - 3]) % MOD;  // 테이블 채우기

    while(t--){ // 각 테스트 케이스마다 n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력
        cin >> n;
        cout << d[n] << "\n";   
    }
}

 

아래는 문제 풀이에 사용된 테스트케이스입니다.

1
1000000
-> 810017797

1
10000
-> 795055102