[BOJ] 15988 - 1, 2, 3 더하기 3

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

난이도: 실버 2

사용언어: JAVA

 

풀이

이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 이 문제를 풀기 위해서는 기본적인 아이디어가 하나 필요합니다.

 

n이라는 값이 주어진다면, n은

 

1 + (n-1) or

2 + (n-2) or

3 + (n-3)

 

으로 표현될 수 있습니다. 다시 말해, n-1을 만드는 경우의 수에 1을 더하면 n이 되고, n-2를 만드는 경우의 수에 2를 더하면 역시 n이 되고, n-3을 만드는 경우의 수에 3을 더하면 이 역시 n이 된다는 것입니다.

 

이를 통해 n을 1, 2, 3의 덧셈을 이용해 조합하는 경우의 수는 [n-1의 경우의 수 + n-2의 경우의 수 + n-3의 경우의 수]임을 알 수 있습니다. 이 아이디어를 다이나믹 프로그래밍을 이용하여 다음과 같이 구현할 수 있습니다.

 

import java.io.*;
 
class Main {
 
    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 i, max = 0;
        int[] arr = new int[T];
        long[] dp; // 다이나믹 프로그래밍을 위한 배열
        for (i = 0; i < T; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }
 
        dp = new long[max + 1]; // 테스트케이스 중 가장 큰 값만큼의 크기의 배열을 생성
        dp[1] = 1; // 1을 만드는 경우의 수는 1 뿐 (1)
        dp[2] = 2; // 2를 만드는 경우의 수는 2 (1+1, 2)
        dp[3] = 4; // 3을 만드는 경우의 수는 4 (1+1+1, 1+2, 2+1, 3)
        for (i = 4; i <= max; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009;
       } // 문제에서 1000000009로 나눈 나머지를 출력하라고 명시했으므로.
 
        for (i = 0; i < T; i++) {
            bw.write(String.valueOf(dp[arr[i]]) + "\n");
        }
        bw.flush();
    }
}