1,2,3 더하기 5

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

1+2+1
1+3
3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제 입력 1

예제 출력 1

3
9
27

마지막 수를 상태에 남기는 이유

단순히 dp[n]을 합 n의 방법 수로 두면 마지막에 1을 붙일 수 있는지 알 수 없다. 직전에도 1을 썼다면 금지되기 때문이다. 그래서 dp[n][last]를 합이 n이고 마지막 수가 last인 방법 수로 둔다. 마지막에 1을 붙이려면 직전 마지막은 2 또는 3이어야 하므로 dp[n][1]=dp[n-1][2]+dp[n-1][3]이다. 마지막 2, 3도 각각 다른 두 마지막 수에서만 이어 온다.

완전한 점화식은 다음과 같다. 오른쪽의 마지막 항을 제거하면 왼쪽에는 해당 합을 만드는 유효한 표현이 남는다. 반대로 그 표현 끝에 다른 수를 붙이면 유효한 표현 하나가 생기므로 중복 계산도 없다.

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

n-last가 음수면 해당 항은 존재하지 않는다. n-last=0일 때는 빈 표현을 마지막 수가 1·2·3 중 무엇인지 분류할 수 없으므로, 한 항짜리 1, 2, 3을 별도로 초기화한다.

한 항만으로 만든 1, 2, 3은 각각 dp[1][1], dp[2][2], dp[3][3]의 초기값 1이다. n=4를 직접 따라가면 1+2+1, 1+3, 3+1의 세 경로가 있다. 1+1+2는 첫 두 항이 같아 제외된다. 결과는 마지막이 무엇이든 가능하므로 dp[n][1]+dp[n][2]+dp[n][3]을 합한다.

합 `n`	마지막 1	마지막 2	마지막 3	전체
1	1	0	0	1
2	0	1	0	1
3	1	1	1	3
4	2	0	1	3

n=4에서 마지막 1의 두 경우는 1+2+1과 3+1이다. dp[4][1] = dp[3][2]+dp[3][3] = 1+1이라는 계산과 맞는다. 예제의 n=7도 같은 방식으로 행을 채우면 9가 된다.

테스트마다 10만까지 다시 계산하면 같은 값을 반복하므로 한 번만 전처리한다. 시간 O(100000+T), 표 공간 O(100000×3)이다. 방법 수는 커질 수 있어 각 상태에서 1,000,000,009로 나누고, 마지막 세 칸을 더할 때는 long을 쓴다. n=1·2·3의 한 항짜리 경우를 빠뜨리지 않는 것이 초기값의 핵심이다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    private static final long MOD = 1000000009L;
    private static final int LENGTH = 100000;
    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());
        long[][] dp = plus123_5();
        while (t-- != 0) {
            int n = Integer.parseInt(in.readLine());
            out.write("" + (dp[n][1] + dp[n][2] + dp[n][3]) % MOD);
            out.write("\n");
        }
        out.flush();
        in.close();
        out.close();
    }

    public static long[][] plus123_5() {
        long[][] dp = new long[LENGTH + 1][4];
        for (int i = 1; i <= LENGTH; i++) {
            dp[i][1] = (i == 1) ? 1 : (dp[i-1][2] + dp[i-1][3]) % MOD;

            if (i - 2 >= 0) {
                dp[i][2] = (i == 2) ? 1 : (dp[i-2][1] + dp[i-2][3]) % MOD;
            }
            if (i - 3 >= 0) {
                dp[i][3] = (i == 3) ? 1 : (dp[i-3][1] + dp[i-3][2]) % MOD;
            }
        }
        return dp;
    }
}