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

문제 URL

https://www.acmicpc.net/problem/15990

다른 풀이

import java.util.*;
public class Main {
    static final long mod = 1000000009L;
    static final int limit = 100000;
    static long[][] d = new long[limit+1][4];
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        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;
        }
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println((d[n][1] + d[n][2] + d[n][3])%mod);
        }
    }
}

느낀점

동적계획법 을 이용한 문제다.

끝내 풀지 못하고 다른사람의 풀이를 참조해서 공부했다.

2차원 배열을 활용하는법 터득

• 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][2] + D[i-3][3]
• 1, 2, 3 더하기에서 한 것 처럼 D[0] = 1로 초기화하면 중복이 발생한다. D[1][1] = D[0][2] + D[0][3] = 2 (중복이 발생하게 된다)
• 따라서, 이 문제는 예외 처리를 해야 한다. D[i][1] • D[i-1][2] + D[i-1][3] (i > 1) • 1 (i == 1) • 0 (i < 1)