[백준 15990 : JAVA] 1, 2, 3 더하기 5 / DP

문제

---

 

 

 

풀이

---

기존의 1, 2, 3 만들기 문제에서 같은 수가 연속해서 오지 못 한다는 조건이 추가되었다.

따라서, 단순히 그 수를 만들기 위한 경우의 수만 저장해가지곤 점화식을 끄집어낼 수 없다.

 

두 가지 정보가 필요하다. 

1. N을 만들기 위한 경우의 수인데,
2. 그 수식의 마지막이 어떤 수로 끝나는 것들.

 

7을 1, 2, 3의 합으로 나타내는 경우의 수를 살펴보자.

1) 7을 만드는 수식 중 마지막이 1로 끝나는 것의 수

6을 만드는 수식 중 마지막이 2로 끝나는 것 + 1

6을 만드는 수식 중 마지막이 3로 끝나는 것 + 1

DP[7][1] = DP[6][2] + DP[6][3]

 

2) 7을 만드는 수식 중 마지막이 2로 끝나는 것의 수

5를 만드는 수식 중 마지막이 1로 끝나는 것 + 2

5를 만드는 수식 중 마지막이 3로 끝나는 것 + 2

DP[7][2] = DP[5][1] + DP[5][3]

 

3) 7을 만드는 수식 중 마지막이 3로 끝나는 것의 수

4를 만드는 수식 중 마지막이 1로 끝나는 것 + 3

4를 만드는 수식 중 마지막이 2로 끝나는 것 + 3

DP[7][3] = DP[4][1] + DP[4][2]

 

위 세 경우를 일반화하면 다음의 점화식이 나온다.

DP[N][1] = DP[N - 1][2] + DP[N - 1][3]

DP[N][2] = DP[N - 2][1] + DP[N - 2][3]

DP[N][3] = DP[N - 3][1] + DP[N - 3][2]

 

 

 

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    private static final int MOD = 1_000_000_009;
    private static int T, N;
    private static long[][] cache;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        cache = new long[100_001][4];
        cache[1][1] = 1;
        cache[2][2] = 1;
        cache[3][1] = 1;
        cache[3][2] = 1;
        cache[3][3] = 1;
        for (int i = 4; i <= 100_000; i++) {
            cache[i][1] = (cache[i - 1][2] + cache[i - 1][3]) % MOD;
            cache[i][2] = (cache[i - 2][1] + cache[i - 2][3]) % MOD;
            cache[i][3] = (cache[i - 3][1] + cache[i - 3][2]) % MOD;
        }

        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            long result = (cache[N][1] + cache[N][2] + cache[N][3]) % MOD;
            sb.append(result).append("\n");
        }

        System.out.println(sb.toString());
    }
}