백준 9764번: 서로 다른 자연수의 합 (DP 활용)

 

목차

1. 문제

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

 

문제

양의 정수 N (1 ≤ N ≤ 2000)을 서로 다른 자연수의 합으로 나타내는 방법은 여러 가지가 있다.  예를 들어:

 

• N = 5인 경우
  • 5
  • 1 + 4
  • 2 + 3 (총 3가지)

 

• N = 6인 경우
  • 6
  • 1 + 5
  • 2 + 4
  • 1 + 2 + 3 (총 4가지)

N이 주어졌을 때, 서로 다른 자연수의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에, 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다.

출력

각 테스트 케이스마다 N을 서로 다른 자연수의 합으로 나타내는 방법의 수 100999로 나눈 나머지를 출력한다.

2. 풀이

📌 문제의 핵심 분석

• 자연수는 중복 사용할 수 없다.
• 조합의 순서가 달라도 같은 것으로 취급한다.
• 즉, 중복 없는 조합(Combination)을 구하는 문제이다.

---

📌 DP(동적 프로그래밍) 접근법

이 문제는 대표적인 DP 문제로 접근할 수 있다. DP를 사용하는 이유는:

• 문제를 작은 부분 문제로 나눌 수 있다.
• 부분 문제의 답을 이용해 큰 문제를 해결할 수 있다.
• 중복 계산을 방지하여 효율적이다.

---

📌 DP 배열 정의

• dp[i]: "서로 다른 자연수의 합으로 숫자 i를 만드는 경우의 수"
• 초기 상태: dp[0] = 1 (합이 0인 경우를 하나로 간주)

---

📌 상태 전이 규칙

숫자 k를 한 번만 사용하는 것을 보장하기 위해, 역순으로 DP 배열을 업데이트한다:

dp[i] = (dp[i] + dp[i - k]) % mod;

이때 mod는 100999로 나눈 나머지를 의미한다.

---

📌 예시 (N = 6)

1. 초기 배열 상태:
   dp = [1, 0, 0, 0, 0, 0, 0]
2. 숫자 1, 2, 3, 4, 5, 6을 차례로 사용하여 배열을 업데이트한 결과:
   최종 dp = [1, 1, 1, 2, 2, 3, 4]
3. 따라서, dp[6] = 4 (답)

3. 코드 구현

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));
        int T = Integer.parseInt(br.readLine());
        int[] arr = new int[T];
        int max = 0;
        for (int i = 0; i < T; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }
        int mod = 100999;
        int[] dp = new int[max + 1];
        dp[0] = 1;

        for (int k = 1; k <= max; k++) {
            for (int i = max; i >= k; i--) {
                dp[i] = (dp[i] + dp[i - k]) % mod;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            sb.append(dp[arr[i]]).append("\n");
        }
        System.out.println(sb);
    }
}

 

4. 정리

📌 시간 복잡도 분석

• 시간 복잡도: O(N²)
• 공간 복잡도: O(N)

---

📌 주의할 점

• dp[i] 접근 시 인덱스 실수 주의 (dp[arr[i]]로 접근해야 한다).
  - 최초 dp[i]로 작성하여 실수를 함
• 입력이 여러 개인 경우, 최대값을 구해 미리 DP 배열을 채우는 방식으로 최적화한다.
  - 테스트 케이스 마다 dp[]를 새로 생성하여 사용 했을때는 132ms으로 나왔고
    최대값을 구해 하나의 dp[]만 사용했을때 100ms으로 개선되었다

---

📌 결론

이 문제를 통해 DP의 기본적인 사용법과 배열을 최적화하여 사용하는 방식을 배울 수 있다. 이 개념은 다른 유사한 DP 문제에도 효과적으로 적용할 수 있다.