문제

image.png

image.png

풀이

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 점화식을 정의하면 아래와 같다.

 dp[n] = 'n를 1,2,3의 합으로 나타내는 방법의 수'

문제에 주어진 예시를 풀어서 보면 아래처럼 나타나지고, 끝자리에 1이오는경우,2가오는경우,3이오는경우로 나눠지는것을 볼 수 있다.

 1 = 1 = 1
 2 = 1+1,2 = 2
 3 = 1+1+1,2+1,1+2,3 = 4
 4 = 1+1+1+1
     1+1+2
     1+2+1
     2+1+1
     2+2
     1+3
     3+1
 (n-3) + 3 = n
 (n-2) + 2 = n
 (n-1) + 1 = n

점화식을 식으로 나타내면 아래와 같다.

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

코드





#include<stdio.h>
#include<algorithm>
using namespace std;
long long dp[1000001];
int main() {

    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    for(int i = 4; i <= 1000001; i++) {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        dp[i] %= 1000000009;
    }

    int t;
    scanf("%d",&t);
    while(t--) {
        int n;
        scanf("%d",&n);
        printf("%lld\n",dp[n]);
    }
    return 0;
}