[백준] 2293 - 동전 1, 2294 - 동전 2 (자바 Java)

[Gold V] 동전 1 - 2293

문제 링크

성능 요약

메모리: 13068 KB, 시간: 128 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2³¹보다 작다.

---

풀이

dp는 왜 해도해도 어려운건지..

2293번은 가능한 경우의 수를 출력하는 문제다.

내가 놓쳤던 것은 n번째 동전을 사용하는 경우의 수를 구할 때 1부터 K까지 모두 구한 후, 다음 n+1번째 동전을 구해야 하는데, 이걸 한꺼번에 구해서 경우의 수가 많이 나왔다는 점이다.

점화식은

dp[n] = dp[n] + dp[n-coin[n]] 이다.
예제에 있는 10의 경우의 수를 구할 때,
동전 2를 사용한 경우는 dp[8]의 값과 같다.
동전 5를 사용한 경우는 dp[5]와 같다.

이걸 동전 n개에 대해 K번 반복하면 값을 구할 수 있다.

package BOJ.Gold.g5;

import java.util.Scanner;

public class BOJ_2293_동전1 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] nums = new int[N];
        for (int i = 0; i < N; i++)
            nums[i] = sc.nextInt();

        int[] dp = new int[K + 1];
        dp[0] = 1;
        for (int n = 0; n < N; n++)
            for (int i = nums[n]; i <= K; i++) {
                dp[i] += dp[i - nums[n]];
            }

        System.out.println(dp[K]);

    }

}

---

[Gold V] 동전 2 - 2294

문제 링크

성능 요약

메모리: 13124 KB, 시간: 136 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

---

풀이

비슷한 문제지만, 최소 개수를 구하는 문제다.

예제에 있는 것처럼 15의 합을 구하는 동전의 개수는

n=1, dp[14]+1

n=5, dp[10]+1

n=12, dp[3]+1

처럼

dp[n] = min(dp[n], dp[n-coin[m]]+1)

이다.

이때 불가능한 경우를 구하려고 n을 Integer.MAX_VALUE로 초기화했다가, 초기값+1이 음수가 되어 올바른 값이 출력되지 않는 문제가 있었다.

dp의 초기값은 k의 최대 범위인 10001로 초기화하면 된다.

package BOJ.Gold.g5;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ_2294_동전2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] nums = new int[N];
        for (int i = 0; i < N; i++)
            nums[i] = sc.nextInt();

        int[] dp = new int[K + 1];
        Arrays.fill(dp, 100001);
        dp[0] = 0;

        for (int n = 0; n < N; n++)
            for (int i = nums[n]; i <= K; i++) {
                dp[i] = Math.min(dp[i - nums[n]] + 1, dp[i]);
            }

        if (dp[K] == 100001)
            System.out.println(-1);
        else
            System.out.println(dp[K]);

    }

}