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

문제 URL

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

나의 풀이

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

public class Main {
    static final int MAX = 1000000;
    static final int MOD = 1000000009;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(bf.readLine());
        int d[] = new int[MAX + 1];
        d[0] = 1;

        for (int i = 1; i <= MAX; i++) {
            for (int j = 1; j <= 3; j++) {
                if (i - j >= 0)
                    d[i] += d[i - j];
                d[i] %= MOD;
            }
        }

        while (size-- > 0) {
            int n = Integer.parseInt(bf.readLine());
            System.out.println(d[n]);
        }
    }
}

느낀점

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

이전에도 풀었던 문제지만 d[0] = 1을 고려를 안해서 계속 오류가 났다. 0->1로 0->2로 0->3으로 바로 더하는 경우도 있어서 고려해야한다.