21.07.13 - [BOJ] 15990. 1, 2, 3 더하기 5

[suhyunsim]

문제

• 1, 2, 3 더하기 5

핵심 아이디어

• 같은 수를 두 번 이상 연속해서 사용하면 안됨
• D[i][j] = i를 1, 2, 3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j
  • D[i][1] = D[i - 1][2] + D[i - 1][3]
  • D[i][2] = D[i - 2][1] + D[i - 2][3]
  • D[i][3] = D[i - 3][1] + D[i - 3][2]
• 정답: D[n][1] + D[n][2] + D[n][3]
• 초기화도 다르게 -> D[1][1], D[2][2], D[3][3]은 각각 1

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q15990;

import java.util.Scanner;

public class Main {
    static final int LIMIT = 100000;
    static final long MOD = 1000000009L;
    static long[][] d = new long[LIMIT + 1][4];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 1; i <= LIMIT; i++) {
            if (i - 1 >= 0) {
                d[i][1] = d[i - 1][2] + d[i - 1][3];
                if (i == 1) {
                    d[i][1] = 1;
                }
            }
            if (i - 2 >= 0) {
                d[i][2] = d[i -2][1] + d[i - 2][3];
                if (i == 2) {
                    d[i][2] = 1;
                }
            }
            if (i - 3 >= 0) {
                d[i][3] = d[i -3][1] + d[i - 3][2];
                if (i == 3) {
                    d[i][3] = 1;
                }
            }
            d[i][1] %= MOD;
            d[i][2] %= MOD;
            d[i][3] %= MOD;
        }
        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println((d[n][1] + d[n][2] + d[n][3]) % MOD);
        }
    }
}