백준 15990번: 1, 2, 3 더하기 5

문제 설명

• 1, 2, 3의 합으로 n을 만들어야 합니다.
• 합은 1개 이상의 수를 사용해 만들 수 있습니다.
• 같은 수를 두 번 이상 연속해서 사용하면 안됩니다.

접근법

• 숫자 n은 n-1에 1을 더하거나 n-2에 2를 더하거나 n-3에 3을 더해서 만들 수 있습니다.
  • n-1에서 1로 끝난 숫자는 1을 더해 n을 만들 수 없습니다.
  • n-2에서 2로 끝난 숫자는 2를 더해 n을 만들 수 없습니다.
  • n-3에서 3으로 끝난 숫자는 3을 더해 n을 만들 수 없습니다.

• 모듈러 연산에 주의해야 합니다.
  • 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());
	}
}

기타

실제로 문제를 풀 때 그린 표