[백준/c++] BOJ 15988 - 1, 2, 3 더하기 3

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

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

 

문제 설명

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구한다.

해결

'1'을 만드는 방법

a. 1

 

'2'를 만드는 방법

a. 1 + 1

b. 2

 

'3'을 만드는 방법

a. 1 + 1+ 1

b. 1 + 2

c. 2 + 1

d. 3

 

'4'를 만드는 방법

a. 1 + 1 + 1 + 1

b. 1 + 2 + 1

c. 2 + 1 + 1

d. 3 + 1

e. 1 + 1 + 2

f. 2 + 2

g. 1 + 3

 

'4'를 만드는 방법을 잘 봐 보자.

a, b, c, d번은 '3'을 만드는 방법에 1을 더한 값이다.

a. 1 + 1 + 1 + 1

b. 1 + 2 + 1

c. 2 + 1 + 1

d. 3 + 1

 

e, f번은 '2'를 만드는 방법에 2를 더한 값이다.

e. 1 + 1 + 2

f. 2 + 2

 

g번은 '1'을 만드는 방법에 3을 더한 것이다.

g. 1 + 3

 

이제 이것을 점화식으로 옮기면

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

이렇게 쓸 수 있다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
#define INF 1e9
using namespace std;

int n, last = 3;
long long dp[1000005];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;

		for (int j = 4; j <= m; j++)
			dp[j] = (dp[j - 1] + dp[j - 2] + dp[j - 3]) % 1000000009;


        cout << dp[m] % 1000000009 << "\n";
    }


}