백준 15988 - 1,2,3 더하기 3

문제

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

리뷰

DP는 정말 언제 풀어도 어려운 것 같다.

로직에서 dp[N]은 1,2,3으로 N을 표현하는 경우의 수를 나타낸다.
$N$이라는 수가 주어졌을때 1,2,3 의 합으로 $N$을 나타내기 때문에,
dp[1], dp[2], dp[3]값만 먼저 초기화 해놓고 dp[N]을 표현할 수 있는 경우는

• dp[N-1]에 1을 더해준 경우
• dp[N-2]에 2를 더해준 경우
• dp[N-3]에 3을 더해준 경우

이렇게 세 가지이므로 아래의 점화식이 성립한다.

로직의 시간복잡도는 $O(N)$의 형태이고, $N$이 최대 100만이므로 주어진
시간 제한 조건 1초를 무난히 통과한다.

문제를 폴며 유의할 점은 모듈러 연산을 해주어도 배열에 담기는 값이 21억
이상일 수 있어 dp 을 타입을 int보다 넓은 범위를 가지는 것으로
설정해야 했다는 점이다. 이 부분 때문에 불필요한 오답을 마주했다.

코드

import java.util.Scanner;

import static java.lang.Integer.parseInt;

public class Main {
    static final int MOD = 1_000_000_009;
    static long[] dp = new long[1_000_001];

    public static void main(String[] args) {
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for (int i = 4; i < dp.length; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD;
        }

        Scanner in = new Scanner(System.in);
        int T = parseInt(in.nextLine());

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int n = parseInt(in.nextLine());
            sb.append(dp[n] + "\n");
        }

        System.out.print(sb);
        in.close();
    }
}

결과