15990: 1,2,3 더하기 5 (DP)

풀이

처음 배열 선언을 int가 아닌 long으로 해줘야 된다는 점이 중요한 문제이다.

1 = 1

2 = 2

3 = 1+ 2, 2+1, 3

4 = 1+ 2+ 1, 1 + 3, 3 + 1

5 = 1 + 3 + 1, 2 + 3, 2 + 1 + 2, 3 + 2

6 = 1 + 2 + 3, 1 + 2 + 1 + 2, 1 + 3 + 2, 2 + 1 + 3, 2 + 1 + 2 + 1, 3 + 2 + 1, 3 + 1 + 2, 2 + 3 + 1

이를 표로 표현해보면

	1	2	3	4	5	6
1	1		1	2	1	3
2		1	1	0	2	3
3			1	1	1	2

4 부터 확인해 보면

dp[n][0] = dp[n-1][1] + dp[n-1][2]

dp[n][1] = dp[n-2][0] + dp[n-2][2]

dp[n][2] = dp[n-3][0] + dp[n-3][1]

임을 확인할 수 있다.

코드

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer buf = new StringBuffer();
		long[][] dp = new long[100000][3];
		long div = 1000000009;

		dp[0][0] = 1;
		dp[0][1] = 0;
		dp[0][2] = 0;

		dp[1][0] = 0;
		dp[1][1] = 1;
		dp[1][2] = 0;

		dp[2][0] = 1;
		dp[2][1] = 1;
		dp[2][2] = 1;

		for (int i = 3; i < 100000; i++) {
			dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % div;
			dp[i][1] = (dp[i - 2][0] + dp[i - 2][2]) % div;
			dp[i][2] = (dp[i - 3][0] + dp[i - 3][1]) % div;
		}

		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			int N = Integer.parseInt(br.readLine());
			buf.append((dp[N - 1][0] + dp[N - 1][1] + dp[N - 1][2]) % div + "\n");
		}
		System.out.println(buf);
	}
}