15990 1, 2, 3 더하기 5

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (추가 시간 없음)	512 MB	16646	5684	3868	31.143%

문제

정수 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

3
4
7
10

예제 출력 1

3
9
27

코드

import java.io.*;

public class P_15990 {

    static long[][] dp;

    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];
        for (int i = 0; i < t; i++) n[i] = Integer.parseInt(br.readLine());
        dp = new long[100001][4];
        dp[1][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;

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

    public static void find_dp() {
        for (int i = 4; i < 100001; i++) {
            dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % 1000000009;
            dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % 1000000009;
            dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % 1000000009;
        }
    }
}

코드 설명

처음에는 dp[n - 1]의 집합에 1을 더하고 dp[n - 2]의 집합에 2를 더해서 구하고 dp[n - 3]의 집합에 3을 더해서 dp[n]의 집합을 구한다는 느낌으로 생각을 했었는데 이 문제는 dp[n - 1], dp[n - 2], dp[n - 3]의 요소가 각각 1, 2, 3 중 어떤 숫자로 끝나는지 알아야만 위 식을 사용할 수 있었다. 그래서 2차원배열로 각 인덱스에 대한 dp의 정보를 추가로 기입했다.

dp[n][1]에는 dp[n]의 요소 중 1로 끝나는 요소의 개수, dp[n][2]에는 2로 끝나는 요소의 개수, dp[n][3]에는 3으로 끝나는 요소의 개수를 저장했다.

이럴 경우 dp[n][1]은 dp[n - 1]의 요소 중 2나 3으로 끝나는 요소를 더한 수와 같다.
dp[3]을 예시로 들면 (1 + 2), (2 + 1), (3) 세 가지가 있는데 여기에 1을 더해서 dp[4]를 만들 수 있는데, (2 + 1)같은 경우는 (2 + 1 + 1)을 할 시 문제의 조건에 위배되게 된다.
따라서, $dp[n][1] = dp[n - 1][2] + dp[n - 1][3]$ 과 같은 식이 나온다.

dp[4][2]는 dp[n - 2] 즉, dp[2]를 봐야 한다. dp[2]의 요소에 2를 더해야 4를 만들 수 있기 때문이다.
dp[2]는 (2) 하나이다.
그런데 2 + 2를 해버리게 되면 문제의 조건에 위배되게 된다.
그렇기 때문에 2를 제외한 dp[2][1]과 dp[2][3]을 더하면 dp[4][2]를 구할 수 있다.
즉, $dp[n][2] = dp[n - 2][1] + dp[n - 2][3]$ 과 같은 식이 나온다.

마지막으로 dp[4][3]은 dp[n - 3], 즉, dp[1]에서 구할 수 있다.
dp[1]은 (1) 하나이다.
이 요소에 1 + 3을 하면 4를 구할 수 있다.
위의 예시에서는 나오지 않았지만 2로 끝나는 요소에 3을 더해도 구할 수 있다.
다만, 3으로 끝나는 요소에 3을 더하게 되면 문제의 조건에 위배되게 된다.
따라서 $dp[n][3] = dp[n - 3][1] + dp[n - 3][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]$

그리고, long을 쓴 이유는 n의 최댓값인 100,000을 넣을 경우 오버플로우가 발생하기 때문이었다.
int만으로 해결을 하기 위해서는 dp[n][1] + dp[n][2] + dp[n][3]을 더하는 과정에서 두 개를 구할 때마다 모듈러 연산을 해야 한다.
그 이유는 dp[n][i]의 최대는 1,000,000,008이고 1,000,000,008 * 3을 할 경우 오버플로우가 발생하기 때문에 두 개를 더할 때마다 모듈러 연산을 해 줘야 오버플로우를 방지할 수 있다.