[백준/15988] 1, 2, 3 더하기 3 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버2
출처 : 백준 - 1, 2, 3 더하기 3

🦧 문제 풀이 접근

사용 가능한 숫자가 1~3까지이므로 dp배열에서 1개 전 값, 2개 전 값, 3개 전 값의 합을 dp에 넣어준다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

💻 code

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

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

        long[] dp = new long[1_000_001];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for(int i=4;i<=1_000_000;i++) {
            dp[i] = (dp[i-1]+dp[i-2]+dp[i-3]) % 1_000_000_009;
        }

        int T = Integer.parseInt(br.readLine());
        while(T-->0) {
            sb.append(dp[Integer.parseInt(br.readLine())]).append("\n");
        }
        System.out.println(sb);
    }
}

🥇 결과

🎓 느낀점

dp에서 많이 틀리는 요소들을 포함하고 있다. long배열 사용, 큰 수 나머지 등.