문제 이해

정수 N을 1,2,3의 합으로만 나타내야 한다.
단, 1,2,3의 숫자 배치는 대칭을 이뤄야한다
(ex. 1 + 2 + 1, 2 + 3 + 2 등)

---

문제 풀이

정수 N을 구하는 문제대로 구할 수 있는 방법은 무엇일까
우리는 N, N-1, ..., 1까지의 답은 알고 있다.

먼저, 맨 뒤에 1을 추가한다고 가정해보자. 이 때 우리는 N을 "대칭"합으로 표현하고 싶기 때문에 맨 앞에도 1이 추가되어야 한다.
즉 2가 더해져야 하는 것이다.

위와 같은 방식으로 N은 총 3가지 방법으로 만들 수 있다.

1. 1 + (N-2을 대칭으로 만듦) + 1

2. 2 + (N-4를 대칭으로 만듦) + 2

3. 3 + (N-6을 대칭으로 만듦) + 3

대칭인 상황에서 양 옆에 같은 수를 붙인다면, 그 수 또한 대칭이라는 것을 활용했다.

즉, DP[N] = DP[N-2] + DP[N-4] + DP[N-6]이 점화식이 될 것이다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static long[] answer = new long[100001];
	static int[] input;
	
	static void dp(int max) {
		answer[4] = answer[2] + answer[0];
		answer[5] = answer[3] + answer[1];
		
		for(int i =6;i<=max;i++) {
			answer[i] 
               = (answer[i-2] + answer[i-4] + answer[i-6]) % 1000000009;
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		int T = sc.nextInt();
		
		answer[0] = 1;
		answer[1] = 1;
		answer[2] = 2;
		answer[3] = 2;
		
		int max = Integer.MIN_VALUE;
		input = new int[T];
		for(int i =0;i<T;i++) {
			input[i] = sc.nextInt();
			max = Math.max(input[i],max);
		}
		dp(max);
		
		for(int i =0;i<T;i++) sb.append(answer[input[i]]% 1000000009)
                                .append("\n");
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2번째 출력 초과 : 결과를 1000000009로 나눈 나머지가 답인데, 실수로 이 과정을 수행하지 않았다.