백준 15988 : 1, 2, 3 더하기 3

​

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

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

 

1 만들 수 있는 경우 : [1] --> 1개

2 만들 수 있는 경우 : [1+1, 2] --> 2개

3 만들 수 있는 경우 : [1+1+1, 1+2, 2+1, 3] --> 4개

4 만들 수 있는 경우 : [1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1] -->7개

5 만들 수 있는 경우 : [1+(4 만들 수 있는 경우), 2+(3 만들 수 있는 경우), 3+(2 만들 수 있는 경우)] --> 13개

n 만들 수 있는 경우 : [(n-1 만들 수 있는 경우), (n-2 만들 수 있는 경우), (n-3 만들 수 있는 경우)] 이므로,

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

 

#include <cstdio>
int main() {
	int n, t;
    long long int dp[1000001] = {0,1,2,4};
	scanf("%d", &t);
	for (int i = 4; i <= 1000000; i++)
		dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009;
	while (t--) {
		scanf("%d", &n);
		printf("%lld\n", dp[n]);
	}
}