[자바] 백준 6220 - Making Change (java)

 문제 : boj6220

---

 

필요 알고리즘 개념

• 동적 계획법 (DP; Dynamic Programming)
  
  • DP로 효율적으로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  얼핏 큰 동전부터 최대한 사용하면 가능할 것이라 생각할 수 있다. 예를들어 예시 1의 경우 25, 50, 10, 1, 5원 이므로 큰 동전부터로 정렬하면 50, 25, 10, 5, 1 이다. 차례대로 사용해서 93 - 50원, 43 - 25원, 18 - 10원, 8 - 5원, 3 - 3 x 1원 으로 될것같이 생겼는데, 사실 서로 배수관계가 아니라면 이런 그리디 풀이는 통하지 않는다. 예를들어 동전이 5원과 2원이 있을 경우, 6원을 표현하려면 5원부터 사용하면 1원이 남으므로 남은 1원을 처리가 불가하고, 2원짜리 3개를 써야 가능하다.

 

  참고로 'All test cases will be solvable using the supplied coins.' 라고 되어있으므로 불가능한 경우는 생각하지 않아도 된다. 그리디하게만 풀지 않으면 가능한 경우는 무조건 있음이 보장된다.

 

  이 문제의 경우 DP로 접근하면 어렵지 않게 풀 수 있다. dp[x]를 'x라는 값을 표현할 수 있는 동전의 최소 갯수'로 정의하자. default값은 dp[0] = 0이고, 그 이외의 값들은 이 문제에서 존재할 수 없는 수치로 정하면 된다. 이 문제에서는 1원짜리 코인만 존재할 경우, C의 최대치인 1000을 표현하기 위해 1000개가 필요하므로 최대 수치는 1000이상으로만 설정하면 된다. 이하 코드에서는 Integer.MAX_VALUE로 정했다.

 

  입력받은 N개의 수치를 각각 arr[0], ..., arr[N-1]이라 해보자. 그리고 dp[1]부터 dp[C] 까지 x를 1부터 C까지 증가시키면서, dp[x-arr[0]], dp[x-arr[1]], ... , dp[x-arr[N-1]] 중 최소값에 1을 더해준 수치가 dp[x] 의 값이 된다. 어떤 의미인지 말로 설명하자면, dp[x] = min(dp[x-arr[y]]) + 1 에 대해 (y는 0부터 N-1) dp[x] 즉 x값을 표현하기 위해 필요한 동전의 최소 개수는, x-arr[y]를 표현할 수 있는 최소 동전 개수에 arr[y]에 해당하는 수치의 동전 하나를 더한 개수라는 의미이다. 최종적으로 dp[C]가 답이다.

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[] dp = new int[1001];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(br.readLine());

        for (int i = 1; i <= c; i++) {
            for (int j = 0; j < n; j++) {
                int target = i-arr[j];
                if (target < 0 || dp[target] == Integer.MAX_VALUE) continue;
                dp[i] = Math.min(dp[i], dp[target]+1);
            }
        }
        System.out.println(dp[c]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}