n-1에 1을 더하거나 n-2에 2를 더하거나 n-3에 3을 더해서
만들 수 있습니다.A+B == (A%C)+(B%C)
이므로 dp에 값을 넣을때마다 모듈러 연산을 실행해 줍니다.A<C,B<C
지만 A+B>C
일 수 있으므로 dp값을 더한 후 한번 더 모듈러 연산을 실행해 줍니다.import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
long[][] dp = new long[100_001][3];
dp[1][0] = 1; // 1
dp[2][1] = 1; // 2
dp[3][0] = 1; // 2+1
dp[3][1] = 1; // 1+2
dp[3][2] = 1; // 3
int divNum = 1_000_000_009;
for (int i = 4; i <= 100000; i++) {
dp[i][0] = (dp[i-1][1] + dp[i-1][2])%divNum;
dp[i][1] = (dp[i-2][0] + dp[i-2][2])%divNum;
dp[i][2] = (dp[i-3][0] + dp[i-3][1])%divNum;
}
StringBuilder sb = new StringBuilder();
for (int t = 0; t < T; t++) {
int n = sc.nextInt();
sb.append((dp[n][0]+dp[n][1]+dp[n][2])%divNum+"\n");
}
System.out.println(sb.toString());
}
}
실제로 문제를 풀 때 그린 표