[BOJ/DP] 백준 2293 - 동전 1 / 2294 - 동전 2 (Java)

2293 - 동전 1

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

문제

n가지 종류의 동전/ 각각의 동전이 나타내는 가치는 다름
동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶음
각각의 동전은 몇 개라도 사용할 수 있음
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우

입력
첫째 줄: n (1 <= n <= 100), k (1 <= k <= 10,000)
n개의 줄에는 각각의 동전의 가치가 주어짐 (자연수) (<= 100,000)
출력: 경우의 수 (<= $2^{31}$)

---

풀이

이전 결과 이용해서 다음 결과 구해야 함

=> 작은 문제의 해를 저장하면서 큰 문제 해결: DP 

 

• `dp[i]`: i원을 만드는 경우의 수
  • `dp[0] = 1`: 0원을 만드는 경우는 아무 동전도 사용 X => 1가지
  • `dp[j] += dp[j - i]`: 현재 금액 j를 만드는 방법은, j - i원 만든 다음에 i 한 번 더 사용

---

코드

import java.io.*;
import java.util.*;

// 동전 1
public class boj_2293 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

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

        for (int i : arr) {
            for (int j = i; j <= k; j++) {
                dp[j] += dp[j - i];
            }
        }

        System.out.println(dp[k]);
    }
}

---

2294 - 동전 2

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

문제

n가지 종류의 동전/ 각각의 동전이 나타내는 가치는 다름
동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶음
각각의 동전은 몇 개라도 사용할 수 있음

입력
첫째 줄: n (1 <= n <= 100), k (1 <= k <= 10,000)
n개의 줄에는 각각의 동전의 가치가 주어짐 (자연수) (<= 100,000)
출력: 사용한 동전의 최소 개수/ 불가능한 경우 -1 출력

---

풀이

• `dp[i]`: i원을 만들기 위한 최소 동전의 개수 
  • `dp[0] = 0`: 0원을 만들기 위해 필요한 동전 수 => 0개
  • `dp[j] = Math.min(dp[j], dp[j - i] + 1)`
    • `dp[j - i] + 1`: j원을 만들기 위해서는 i를 하나 더 사용하면 됨 -> +1

---

코드

import java.io.*;
import java.util.*;

// 동전 2
public class boj_2294 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int INF = 10_001;
        int[] dp = new int[k + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int i : arr) {
            for (int j = i; j <= k; j++) {
                dp[j] = Math.min(dp[j], dp[j - i] + 1);
            }
        }

        System.out.println(dp[k] == INF ? -1 : dp[k]);
    }
}