백준 [15990] 1, 2, 3 더하기 5 (자바)

문제

입력

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

출력

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

풀이

예시에서 4를 만드는 경우를 보면 3을 만드는 경우의 수에서 1을 붙여서 만들 수 있다.

3을 만드는 케이스에서 1을 붙여서 4를 만드는 경우

1+2+1

2+1+1 -> 같은 수를 2번 이상 사용한 경우라서 경우의 수에 포함되지 않는다.

3+1

 

2를 만드는 케이스에서 2를 붙여서 4를 만드는 경우

2+2 같은 수를 두 번 붙여 포함 x

 

1을 만드는 케이스에서 3을 붙여서 4를 만드는 경우

1+3

 

4를 만드는 경우의 수는 2차원 배열을 이용해서 표현할 수 있다.

끝이 1로 끝나는 연산의 경우의 수가 2개 -> dp[4][1] = 2

끝이 2로 끝나는 연산의 경우의 수가 0개 -> dp[4][2] = 0

끝이 3로 끝나는 연산의 경우의 수가 1개 -> dp[4][3] = 1

총 3개이다.

 

 

이와 같이 5를 적용해보면

(5를 만드는 케이스 중 1로 끝나는 연산의 경우는) = (4를 만드는 연산 뒤에 1로 끝나지 않는 경우의 연산에서 1를 붙인 케이스의 경우들)

dp[5][1] = dp[4][2] + dp[4][3] = 0+1 = 1 (1+3+1)

 

(5를 만드는 케이스 중 2로 끝나는 연산의 경우는) = (3을 만드는 연산 뒤에 2로 끝나지 않는 경우의 연산에서 2를 붙인 케이스의 경우들)

dp[5][2] = dp[3][1] + dp[3][3] = 1+1 = 2 (2+1+2, 3+2)

 

(5를 만드는 케이스 중 3으로 끝나는 연산의 경우는) = (2을 만드는 연산 뒤에 3으로 끝나지 않는 경우의 연산에서 3을 붙인 케이스의 경우들)

dp[5][3] = dp[2][1] + dp[2][2] = 0+1 = 1 (2+3)

 

그럼 5를 만드는 경우의 수 중 같은 수를 연속해서 사용하지 않고 연산이 가능한 경우는 3가지 케이스의 합인 4가 된다.

 

점화식

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

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

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

 

마지막에 한번 더 1000000009 값을 나눠주는 이유를 몰랐는데 찾아보니 중간 연산에서 dp[N][1],dp[N][2],dp[N][3]의 값이 1000000009보다 클 수 있어서 오버플로우 방지를 위해 한번 더 나눠줌으로서 나머지 값이 1000000009로 나눌 수 있는 범위를 보장한다고 한다.

정답코드

package com.baekjoon.p15990;

import java.io.*;

public class Main {
    static final int num = 100001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long[][] dp = new long[num][4];

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

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

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            long ans = (dp[N][1] + dp[N][2] + dp[N][3]) % 1_000_000_009;

            sb.append(ans).append("\n");
        }

        System.out.print(sb);
    }
}