15988 1, 2, 3 더하기 3

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (추가 시간 없음)	512 MB	17799	6524	4880	35.118%

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

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

입력

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

출력

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

예제 입력 1

3
4
7
10

예제 출력 1

7
44
274

코드

import java.io.*;

public class P_15988 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        int[] n = new int[t + 1];
        for (int i = 1; i <= t; i++) n[i] = Integer.parseInt(br.readLine());
        long[][] dp = new long[1000001][4];

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

        for (int i = 1; i<= t; i++) {
            bw.write(Long.toString((dp[n[i]][1] + dp[n[i]][2] + dp[n[i]][3]) % 1000000009));
            bw.newLine();
        }
        bw.flush();
    }
}

코드 설명

n을 1, 2, 3만으로 나타내기 위해서는 n - 1을 1, 2, 3으로 나타낸 경우에 + 1을 해 주거나, n - 2를 1, 2, 3으로 나타낸 경우에 + 2를 해 주거나, n - 3을 1, 2, 3으로 나타낸 경우에 + 3을 해 주는 방법이 있다.

예를 들어서 4를 1, 2, 3만으로 나타내기 위해서는 3을 1, 2, 3으로 나타낸 방법에 1을 더하는 방법이 있다.
3을 1, 2, 3으로 나타낸 방법은

• 1 + 1 + 1
• 1 + 2
• 2 + 1
• 3
  이 있는데, 위 각각의 경우에 + 1만 해주면 4를 나타낼 수 있게 된다.
  그리고 2를 1, 2, 3으로 나타낸 방법에 + 2를 더하는 방법이 있다.
  2를 1, 2, 3만으로 나타낸 방법에는
• 1 + 1
• 2
  가 있는데 위 각각의 경우에 + 2를 해 주게 되면 4를 나타내는 방법이 된다.
  마지막으로 1을 1, 2, 3으로 나타낸 경우에 + 3을 해 주는 방법이 있다.
  1은 1로만 나타낼 수 있는데 여기에 + 3을 하게 되면 4가 된다.

즉, 점화식은 다음과 같다.

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

이차원배열로 선언한 이유는 1 + 2와 2 + 1이 다른 조합으로 인식되기 때문인데 이걸 계산하기 위해서는 n - i의 숫자의 조합이 1로 끝나는지 2로 끝나는지 3으로 끝나는지를 알아야 하기 때문이다.

그래서 dp[i][j]에서 i는 구할 숫자를 의미하고, j는 1, 2, 3으로 끝나는 수가 각각 몇 개인지를 나타낸다.
dp[i][1] + dp[i][2] + dp[i][3]은 i에 대한 수를 1, 2, 3으로 나타낸 방법의 총 집합이 된다.

dp[0][3]을 1로 설정한 이유는 dp[3][3]에 관한 식을 구하면서 n - 3시 0에 참조하는 문제가 생기기 때문에 초기화를 그렇게 해 두었다. dp[3][3]은 dp[0][1] + dp[0][2] + dp[0][3] 식으로 구하므로 dp[0][1], dp[0][2], dp[0][3] 중 아무거나 하나만 1로 초기화한다면 결과는 같다.

dp를 long으로 설정한 이유는 int로 설정할 경우 두 개를 더할 때마다 1000000009로 나눠주기 귀찮기 때문이다.
int로 설정하고 세 개의 합을 구한 후 1000000009로 나눠주면 가장 최악의 경우에 int의 범위를 넘어간다.
어떤 수를 1000000009로 나누었을 때 최댓값은 1000000008이고, dp[i][1], dp[i][2], dp[i][3]이 모두 1000000008이라고 가정했을 때 세 개를 더하게 되면 3000000024이 되면서 int의 최댓값 범위인 2147483647을 넘게 된다.
그래서 int로 설정을 하게 되면 dp[i][1] + dp[i][2]를 한 후 1000000009로 나눠주고, 이 결과값에 dp[i][3]을 더한 후 다시 1000000009로 나눠준 값이 답이 되게 된다.