문제 이해

정수 N을 1,2,3의 합으로 나타내야 한다.
이 때 같은 수를 두 번 연속으로 더할 수는 없다.
(예를 들어, 2 = 1+1인데 1이 연속으로 더해질 수 없으므로 경우의 수로 포함하지 않는다)

이런 제한 조건 아래서의 경우의 수를 구하는 문제이다.

---

문제 풀이

1,2,3 더하기 N의 문제 풀이와 비슷하게 했다.
단지, 마지막에 더해지는 값에 따라 공간에 값을 저장하는 방식으로 활용했다.

즉, "DP[i][j] = i를 만들 때 j를 가장 마지막에 더하는 경우의 수"로 문제를 풀었다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static long[][] DP;
	static final int MOD = 1000000009;
	//DP[j][i] : j를 마지막으로 더하여 i를 만드는 총 경우의 수
	
	static void dp() {
		DP[1][1] = 1;
		DP[2][2] = 1;
		DP[1][3] = 1;
		DP[2][3] = 1;
		DP[3][3] = 1;
		
		for(int i =4;i<100001;i++) {
			for(int j=1;j<4;j++) {
				for(int k=1;k<4;k++) {
					if(k==j) continue;
					DP[j][i] += DP[k][i-j];
					DP[j][i] %= MOD;
                    // i = (i-j) + j로 만들 수 있다.
                    // 이 때, (i-j)를 만들 때 가장 마지막에 더해진 값이 
                    // j이면 안된다.
                    // 따라서, k=j인 경우는 무시하고 
                    // 나머지 경우의 수는 모두 더해주었다.
				}
			}
		}
	}
	
	static void find() {
		long ans = (DP[1][N] + DP[2][N] + DP[3][N])%MOD;
		
		sb.append(ans).append("\n");
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		int T = sc.nextInt();
		DP = new long[4][100001];
		dp();
		
		for(int t=0;t<T;t++) {
			N = sc.nextInt();
			find();
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2번째 줄 시간 초과 : dp 메서드의 for문 시행 수를 실수로 0을 하나 더 붙여 너무 많은 수행이 되었다.