백준 9095·15988 Java: 1, 2, 3 더하기 DP의 공통점과 차이

백준 9095번과 15988번은 모두 정수 n을 1, 2, 3의 합으로 나타내는 순서 있는 방법의 수를 묻는다. 원문에서는 15988번을 재귀로 작성했다가 시간 초과를 겪고 반복문 DP로 바꿨다.

• 백준 9095번 1, 2, 3 더하기
• 백준 15988번 1, 2, 3 더하기 3

점화식은 같지만 입력 범위와 나머지 연산이 다르다. 이 차이를 분리해 두면 작은 문제의 풀이를 큰 문제에 그대로 옮길 때 생기는 실수를 막을 수 있다.

마지막에 더한 수로 경우를 나누기

dp[n]을 n을 만드는 방법의 수라고 하자. 마지막 수는 1, 2, 3 중 하나다.

마지막이 1이면: dp[n - 1]
마지막이 2이면: dp[n - 2]
마지막이 3이면: dp[n - 3]

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

dp[0] = 1은 아무 수도 고르지 않은 한 가지 방법을 뜻한다. 이 기준을 두면 dp[1], dp[2], dp[3]을 별도 암기하지 않고 같은 전이로 만들 수 있다.

9095 Java 코드

9095번은 입력 n이 작고 나머지 연산이 없다. 여러 test case 중 최댓값까지만 미리 계산한다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int testCount = Integer.parseInt(reader.readLine());
        int[] query = new int[testCount];
        int max = 0;

        for (int test = 0; test < testCount; test++) {
            query[test] = Integer.parseInt(reader.readLine());
            max = Math.max(max, query[test]);
        }

        int[] dp = new int[max + 1];
        dp[0] = 1;
        for (int total = 1; total <= max; total++) {
            for (int last = 1; last <= 3; last++) {
                if (total >= last) {
                    dp[total] += dp[total - last];
                }
            }
        }

        StringBuilder answer = new StringBuilder();
        for (int value : query) {
            answer.append(dp[value]).append('\n');
        }
        System.out.print(answer);
    }
}

15988 Java 코드

15988번은 n이 훨씬 크고 결과를 1,000,000,009로 나눈 나머지를 요구한다. 세 항을 더하면 int 범위를 넘을 수 있으므로 DP 배열을 long으로 두었다.

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

public class Main {
    private static final long MOD = 1_000_000_009L;

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int testCount = Integer.parseInt(reader.readLine());
        int[] query = new int[testCount];
        int max = 0;

        for (int test = 0; test < testCount; test++) {
            query[test] = Integer.parseInt(reader.readLine());
            max = Math.max(max, query[test]);
        }

        long[] dp = new long[max + 1];
        dp[0] = 1;

        for (int total = 1; total <= max; total++) {
            for (int last = 1; last <= 3; last++) {
                if (total >= last) {
                    dp[total] = (dp[total] + dp[total - last]) % MOD;
                }
            }
        }

        StringBuilder answer = new StringBuilder();
        for (int value : query) {
            answer.append(dp[value]).append('\n');
        }
        System.out.print(answer);
    }
}

재귀가 맞는 점화식이어도 안전하지 않을 수 있다

원문의 재귀 버전에도 memoization이 있었으므로 같은 상태를 무한히 다시 계산한 것은 아니다. 다만 15988번처럼 n이 최대 백만까지 커지면 재귀 깊이 자체가 Java stack이 감당할 범위를 벗어난다. 함수 호출 비용만의 문제가 아니라 실행 구조가 입력 범위와 맞지 않는다.

작은 예제로 재귀 관계를 찾은 뒤, 큰 범위에서는 bottom-up 반복문으로 옮기는 편이 안전하다. 입력을 먼저 모두 읽고 최댓값까지만 계산하면 매 test case마다 같은 DP를 다시 만들 필요도 없다.

다른 상태 정의가 필요한 DP는 백준 9465 스티커, 피보나치 재귀와 DP의 실행 횟수 차이는 백준 24416 피보나치 수 1에서 이어서 볼 수 있다.

검증 범위

Java source를 수동 검토했다. 작은 n의 모든 1·2·3 순서 조합을 직접 열거한 값과 두 DP를 대조하고, 15988번은 큰 n에서도 모든 원소가 나머지 범위 안에 있는지 확인한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.