[백준] 9764 서로 다른 자연수의 합 - Dynamic Programming / Java

• 문제 링크

9764번: 서로 다른 자연수의 합

 

• 풀이 과정

문제에 주어진 n 의 최대 범위 2000까지 방법의 수를 구할 수 있지만,

해당 풀이에서는 입력의 최대 값 범위까지 방법의 수를 구한다.

 

 j 를 만들 수 있는 1 ~ i 까지의 서로 다른 자연수의 합의 방법의 수를 구한다고 할 때,

예시로 dp[[0] = 1, n = 6 일 경우 아래와 같이 도출된다.

j	i	dp[j - i]	dp[j] = dp[j] + dp[j - i]
6	1	dp[5] = 0	dp[6] = 0
5	1	dp[4] = 0	dp[5] = 0
4	1	dp[3] = 0	dp[4] = 0
3	1	dp[2] = 0	dp[3] = 0
2	1	dp[1] = 0	dp[2] = 0
1	1	dp[0] = 1	dp[1] = 0 + 1 = 1
6	2	dp[4] = 0	dp[6] = 0
5	2	dp[3] = 0	dp[5] = 0
4	2	dp[2] = 0	dp[4] = 0
3	2	dp[1] = 1	dp[3] = 0 + 1 = 1
2	2	dp[0] = 1	dp[2] = 0 + 1 = 1
6	3	dp[3] = 1	dp[6] = 0 + 1 = 1
5	3	dp[2] = 1	dp[5] = 0 + 1 = 1
4	3	dp[1] = 1	dp[4] = 0 + 1 = 1
3	3	dp[0] = 1	dp[3] = 1 + 1 = 2
6	4	dp[2] = 1	dp[6] = 1 + 1 = 2
5	4	dp[1] = 1	dp[5] = 1 + 1 = 2
4	4	dp[0] = 1	dp[4] = 1 + 1 = 2
6	5	dp[1] = 1	dp[6] = 2 + 1 = 3
5	5	dp[0] = 1	dp[5] = 2 + 1 = 3
6	6	dp[0] = 1	dp[6] = 3 + 1 = 4

이처럼 각 자연수 j 를 만들기 위한 자연수 범위 i 를 확장시켜 구해가며,

현재 값에 dp[j -i] 값을 누적해 방법의 수를 구한다.

 

이 후 입력받은 각각의 자연수에 대한 해를 dp 배열에서 참조해 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] arr = new int[Integer.parseInt(br.readLine())];
        int max = 0;

        for (int i = 0; i < arr.length; i++)
            max = Math.max(max, arr[i] = Integer.parseInt(br.readLine()));

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

        for (int i = 1; i < dp.length; i++) {
            for (int j = max; j >= i; j--)
                dp[j] = (dp[j] + dp[j - i]) % 100999;
        }

        StringBuilder sb = new StringBuilder();
        for (int n : arr)
            sb.append(dp[n]).append("\n");

        bw.write(sb.toString());
        bw.flush();
    }

}