[BOJ 15989] 1, 2, 3 더하기 4 - Java (동적 계획법 순서 없는 분할 DP)

1. 문제 개요 및 조건 분석

항목	내용
문제 이름	1, 2, 3 더하기 4 (백준 15989번 / 실버 1)
플랫폼 / 난이도	백준 (실버 1, 15989번)
문제 링크	백준 15989번
제한 사항	시간 제한 1초, 메모리 제한 512MB
입력 조건	테스트 케이스 수 $T$, 정수 $n \le 10,000$
핵심 규칙	정수 $n$을 1, 2, 3의 합으로 나타내는 방법의 수 (합을 이루는 수의 순서만 다른 것은 하나로 인정)

---

2. 접근 아이디어: 동전 교환형 1차원 DP (조합 중복 방지)

순서가 없는 합(조합)을 구하는 DP 원리

• '1, 2, 3 더하기 1'과 달리, 이 문제는 순서만 다른 것을 같은 것으로 취급합니다 ($1+2$와 $2+1$은 동일).
• 이는 동전 1, 2, 3원을 사용해 거스름돈 $n$원을 만드는 동전 교환 문제와 완전히 동일합니다.
• 순서 중복을 원천 차단하기 위해 사용할 숫자(1 $\to$ 2 $\to$ 3)를 단계별로 순차 적용합니다:
  1. 1만 사용하는 경우: 모든 $i$에 대해 방법은 단 1가지 (dp[i] = 1).
  2. 2를 추가로 사용하는 경우: $i \ge 2$부터 dp[i] += dp[i - 2].
  3. 3을 추가로 사용하는 경우: $i \ge 3$부터 dp[i] += dp[i - 3].

---

3. Java 풀이 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());

        // n <= 10000에 대해 DP 테이블 사전 계산
        int[] dp = new int[10001];
        dp[0] = 1;

        // 1, 2, 3을 순서대로 반영하여 조합 중복 방지
        for (int coin = 1; coin <= 3; coin++) {
            for (int i = coin; i <= 10000; i++) {
                dp[i] += dp[i - coin];
            }
        }

        StringBuilder sb = new StringBuilder();
        while (tc-- > 0) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append("\n");
        }

        System.out.print(sb);
    }
}

---

4. 복잡도 분석

• 시간 복잡도: $O(N + T)$ — DP 전처리 $3 \times 10,000 = 30,000$ 연산 후 질의당 $O(1)$ 반환.
• 공간 복잡도: $O(N)$ — 크기 10,001의 1차원 DP 배열.

---

5. 채점 결과 및 통과 인증