[백준] 15988번. 1, 2, 3 더하기 3(JAVA)

문제

https://www.acmicpc.net/problem/15988

---

풀이(15분)

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine()); // 반복 횟수

        long[] dp; // 메모이제이션을 사용할 배열
        // 하단 부분의 dp를 3개 더하는 경우가 있는데
        // 이 떄 1,000,000,009의 나머지이기 때문에 세개를 합할 경우 int범위 초과 가능
        // 다운 캐스팅을 사용하지 않으려고 처음부터 long 으로 선언

        for(int i = 0; i < t; i++){
            int n = Integer.parseInt(br.readLine());
            if(n < 3){ // 만약 dp가 들어가지 않아도 될 범위라면 바로 응답
                dp = new long[4];
                dp[1] = 1;
                dp[2] = 2;
                dp[3] = 4;
                System.out.println(dp[n]);
                continue;
            }
            dp = new long[n+1];
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;
            for(int j = 4; j < n + 1; j++){ // dp 에 대한 점화식
                dp[j] = (dp[j-1] + dp[j-2] + dp[j-3]) % 1000000009;
            }
            System.out.println(dp[n]);
        }
    }
}

 

dp를 사용한 간단한 문제였다.

 

dp를 쓰는 방식대로 경우를 하나씩 서술해 가며 분석하여 이 전 3개의 항에 대한 합이라는 것을 알아냈다.

 

코드에 작성해둔 대로 dp를 애초에 long으로 저장해 둔 이유는 int범위를 넘어서기 때문이 아닌 하단의 3개의 합 부분에서 int 범위를 넘을 수 있기 때문이다. 물론 각각에 대해 다운캐스팅을 해주어도 되지만 메모리 여유도 있고, 문제를 빨리 해결하고 싶어 그렇게 하지는 않았다.

 

또한, 처음 제출할 때 아무 생각 없이 n < 3에 대한 경우를 return;으로 처리하여 문제가 발생하였다. 반복적인 검사를 위해 continue로 변경하였다.