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

 

1) 문제설명

백준 Online Judge 15988번 1, 2, 3 더하기 3

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

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

 

2) 아이디어

1을 만들기 위해 필요한 1,2,3의 값은

dp [1] = 1 (1)

2를 만들기 위해 필요한 1,2,3의 값은

dp [2] = 2 (1+1) (2)

3을 만들기 위해 필요한 1,2,3의 값은

dp [3] = 4 (1+1+1) (1+2) (2+1) (3)

이때 4를 만들기 위해 필요한 1,2,3의 값을 살펴보면

1+1+1+1 -> (1+1+1 +1)

1+2+1 -> (1+2 +1)

2+1+1-> (2+1 +1)

3+1 ->(3 +1)

1+1+2 -> (1+1 +2)

2+2 ->(2 +2)

1+3  -> (1 +3)

dp [4]는 dp [3], dp [2], dp [1]에서 영향을 받는다

즉, 4를 만들기 위해서는 3을 만드는 방법에서 +1을 붙이고, 2를 만드는 방법에서 +2를 붙이고, 1을 만드는 방법에서 +3을 붙이는 방법으로 dp의 식을 세운다.

 

3) 코드

using namespace std;
// dp[n] : n을 1,2,3의 합으로 나타내는 방법의 수
long long dp[1000001];
int arr[1000001];
int main() {
	int t;
	int cnt = 0;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		cin >> arr[i];
	}
	dp[1] = 1;
	dp[2] = 2; // 1+1, 2
	dp[3] = 4; // 1+1+1 , 1+2, 2+1, 3
	dp[4] = 7; // 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1
	for (int i = 4; i <= 1000001; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009;
	}
	for (int i = 1; i <= t; i++) {
		cout << dp[arr[i]] << endl;
	}