자바(백준) 15988 1, 2, 3 더하기 3

오답 노트 & 새로 알게 된 점

해당 문제는 1, 2, 3 더하기 1을 풀면 똑같은 점화식을 가진다는 것을 알 수 있다.

 

하지만 이 문제의 함정은 n의 범위이다. 1에서는 아마 n의 범위가 11보다 작은 정수였는데, 해당 문제는 n이 1,000,000보다 작거나 같은 정수(양수)이다. 그리고 1,000,000,009로 나눈 나머지를 출력한다고 한다.

 

처음에 문제를 똑같이 풀 때에는 당연히 1과 똑같이 코드를 제출했다. 그냥 n의 범위가 다른가 보다 하고 말이다. 하지만 당연하게 틀렸습니다가 나왔다.

 

나는 저 10억으로 나눈 나머지를 출력한다 이 부분을 간과하였다. 이 말은 즉, 어디가 10억이 넘는 곳이 있다라는 말이었고, 배열의 범위를 int로 하면 안 되는 것이었다. 만약 점화식에서 dp[i-3], dp[i-2], dp[i-1]이 각각 10억, 10억, 10억이 되면 int의 범위를 넘어서기 때문이다. 그래서 dp배열의 형을 long으로 해줘야 한다. 

 

코드

package Dynamic_Programming;
 
import java.util.*;
import java.io.*;
 
public class BOJ15988 {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
 
        long dp[] = new long[1000001];
 
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
 
        for(int i = 4; i < 1000001; i++){
            dp[i] = (dp[i-3] + dp[i-2] + dp[i-1]) % 1000000009;
        }
 
        int test = s.nextInt();
 
        while(test-- > 0){
            int num = s.nextInt();
 
            System.out.println(dp[num]);
        }
    }
}