백준 15991 : 1, 2, 3 더하기 6

주어진 정수 N을 1, 2, 3의 합으로 나타내는 경우의수를 구하는 문제이다. 단, 합은 대칭을 이루어야 한다.

---

 

DP 문제는 의외로 간단하다. 양쪽을 1, 2, 3으로 감싸는 방식을 생각하면 편하다. 예를 들어 dp[8]을 구할 때는 1 + 6을 구하는 방법 + 1, 2 + 4를 구하는 방법 + 2, 3 + 2를 구하는 방법 + 3으로 접근할 수 있다. 이를 바탕으로 점화식은 dp[i] = dp[i - 2] + dp[i - 4] + dp[i - 6]으로 세울 수 있다. 이 방식으로 문제를 해결할 수 있지만, 초기값을 6까지 설정해야 해서 다소 번거로울 수 있다.

 

<소스코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define MOD 1000000009;
int dp[100010];

int main()
{
    int i, j;
    int t;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 2;
    dp[4] = 3;
    dp[5] = 3;
    dp[6] = 6;
    for(i=7;i<=100000;i++) {
        int res = (dp[i - 2] + dp[i - 4]) % MOD;
        res = (res + dp[i - 6]) % MOD;
        dp[i] = res;
    }
    scanf("%d", &t);
    while(t--) {
        int x;
        scanf("%d", &x);
        printf("%d\n", dp[x]);
    }
    return 0;
}