[Java] 백준 15988 1, 2, 3 더하기 3

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

난이도

실버2

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

내 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer T = Integer.parseInt(br.readLine());

		ArrayList<Integer> arr = new ArrayList<>();
		int max = 0;
		for (int t = 0; t < T; t++) {
			int tmp = Integer.parseInt(br.readLine());
			arr.add(tmp);
			max = Math.max(max, tmp);
		}

		int MOD = 1000000009;
		int[] dp = new int[max + 1];
		dp[1] = 1;
		if (max >= 2) dp[2] = 2;
        if (max >= 3) dp[3] = 4;
        
		for(int i = 4; i <= max; i++) {
			dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
		}
		
		StringBuilder sb = new StringBuilder();
		for(int a : arr) {
			sb.append(dp[a]).append('\n');
		}
		
		System.out.println(sb);
	}
}

입력으로 주어지는 값 중에 최댓값을 찾고 DP 배열의 크기를 찾는다.

DP를 채워넣기 위해서 ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD 점화식을 세우면 된다.

처음에 한번 틀렸는데 그 이유는 점화식을 dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD이렇게 세웠는데 한번에 다 더하고 나눠서 오버플로우가 발생한 것 같다.

dp[i-1], dp[i-2], dp[i-3]의 값이 매우 커지면, dp[i-1] + dp[i-2] + dp[i-3]이 int 범위를 초과하게 된다. 이로 인해 음수 값이 발생하거나 올바르지 않은 값이 나올 수 있기 때문에 틀린 것 같다.