15990번. 1, 2, 3 더하기 5

 

아이디어

정수 n 에 대해서 n - 1 + 1, n - 2 + 2, n - 3 + 3 의 방법을 활용하면 1, 2, 3 의 합으로 나타내는 방법을 구할 수 있다. 다만 연속해서 같은 수를 사용하면 안 되기 때문에 n - 1 + 1 에 대해서 (n - 1) 은 (n - 3 + 2) 또는 (n - 4 + 3) 으로 구성이 되어야 한다.

 

따라서 아예 마지막에 j 를 더해서 i 을 만드는 경우의 수를 저장하는 배열을 만들어

 

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

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

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

 

와 같이 점화식을 만들어 계산을 한 뒤 dp[i][1] + dp[i][2] + dp[i][3] 을 합하면 i 를 1, 2, 3 의 합으로 나타내는 방법의 수를 구할 수 있다.

 

추가로 방법의 수를 1_000_000_009로 나눈 나머지를 출력해야 하므로 모듈러 연산을 활용하면 된다.

 

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

        int[][] dp = new int[100001][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 <= 100000; 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();
        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(((dp[n][1] + dp[n][2]) % 1_000_000_009 + dp[n][3]) % 1_000_000_009).append("\n");
        }

        System.out.println(sb);
    }
}