알고리즘) 동전 교환(냅색 알고리즘)

문제 ✨

 N개의 여러 단위 동전이 주어질 때 거스름돈 M을 거슬러 줄 동전의 최소 개수를 구해라

 Cf. 첫 번째 줄에는 동전 종류 수 N(1 <= N <= 50), 두 번째 줄에는 N개의 동전 종류, 마지막 줄에는 거슬러줄 금액 M(1 <= M <= 500) 가 입력된다.

 

풀이 ✨

 DFS로도 풀 수 있지만, N값 범위가 커지면 1초 Time Limit에 걸려 DP(Dynamic Programming)으로 풀어야 한다. 처음에는 아주 단순한 방법으로 가능할 것으로 생각했다. 입력받은 수들을 내림차순으로 정렬해 루프를 돌고, 주어진 수 total를 해당 순서의 수로 나눈 몫이 해당 동전의 수가 되고, total 값을 해당 순서의 수로 나눈 나머지값이 되게 하면 될 것이라 생각했다. 하지만 예외의 경우가 있음을 확인하면서 전제가 잘못되었다는 생각을 하게 되었다.

 예를 들어, total값이 129이고, 동전의 종류가 1, 8, 20, 25, 50인 경우를 보자. 내가 처음에 생각했던 방식대로라면 129는 50 * 2 + 25 * 1 + 20 * 0 + 8 * 0 + 1 * 4 가 될 수 있다. 그러면 동전의 개수는 7개가 된다. 하지만 이 결과가 아닌 50 * 2 + 25 * 0 + 20 * 1 + 8 * 1 + 1 * 1 의 경우에도 나눠떨어지며, 이 때는 동전의 개수가 5개로 이전에 구했던 개수보다 작다. 좀 더 다이나믹하게 생각해볼 필요가 있는 것 같다.

 result 라는 배열을 만들되, 이 배열의 크기를 total 으로 만든다. 이 배열의 i번째 인덱스의 값은 i라는 금액을 만드는데 필요한 최소 동전 개수라고 한다. 최종적으로는 result[total] 의 값을 출력하면 되는 것이다.

 배열 result 의 모든 요소 값을 Integer.MAX_VALUE 로 두고, result[0]의 값으로는 0을 부여한다. 그리고는 동전의 종류 만큼 반복을 수행한다. 이 때 이 반복(루프) 내부에서 result 의 요소들의 값이 변경될 수 있을 때마다 더 작은 값이 해당 인덱스의 값이 될 수 있게 한다.

 동전의 종류로 만든 배열인 coin 이 존재한다. 그렇다면 아래와 같이 반복문이 돌게 될 것이다. 그렇다면 i가 1일 때는 배열 요소들(의 값)이 곧 인덱스가 될 것이다.

int[] coin = new int[n + 1];
// coin 요소 입력받는 과정 생략

for (int i = 1; i <= n; i++) {
	... // 각 동전만으로 해당 값(인덱스)를 만드는 데에 필요한 동전의 수 구하기
}

 i가 2가 되면 어떨까? 2이하의 인덱스는 반복하지 않아도 된다. 어차피 2원짜리 동전으로는 해당 금액을 만들 수 없기 때문이다. (0개가 들 수는 있지만 결국 음수의 동전이 있지 않는 이상 해당 금액을 만들 수 있는 것은 아니기 때문에 ‘0이 최솟값이니 바꿔야 한다’고 생각하지 않는다.)

 i가 2일때를 생각해보자. j라는 금액을 만들기 위한 동전의 개수를 구하기 위해서는 result[j]를 구해야 하는데, 이를 result[j - coin[i]] + 1이라고 바꿔보겠다. 이 의미는 j원을 만들기 위한 동전 개수는 곧, (j - 동전 금액)을 만드는 동전 개수 + 1과 같다. 무슨 말인고 하니, 뒤에 1을 더해주도록 하고 만들어야 하는 금액을 해당 동전 하나 금액 만큼 뺀 값이다. 이렇게 접근하는 것은 이미 값을 구한 인덱스들의 값을 사용할 수 있기 때문이다.

 i가 2라면 반복문은 2부터 시작하되, 이 2라는 금액을 2원짜리 동전으로 만들기 위해서필요한 동전 수는 1이다. 이는 ‘0이라는 금액을 2원짜리 0개로 만드는데 드는 동전 수’에서 1 더한 값과 같다. 즉, 앞서 정의한 반복문 내부에서 돌아야 하는 반복문을 아래와 같이 구체화 될 수 있다. (내가 알고리즘을 이해한 방식)

 이러한 방식으로 반복문을 다 돌고나면 입력받은 total 금액을 만들기 위한 동전의 최소 개수인 result[total]을 출력할 수 있을 것이다.

for (int i = 1; i <= n; i++) {
	for (int j = list[i]; j <= total; j++) {
		result[j] = Math.min(result[j], result[j - list[i]] + 1); 
	}
}

 

1차 작성 코드(실패) ✍️

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

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Integer[] list = new Integer[n];
    int[] cnt = new int[n];
    for (int i = 0; i < n; i++) list[i] = sc.nextInt();
    int total = sc.nextInt();

    Arrays.sort(list, Collections.reverseOrder());
    int temp = total;
    for (int i = 0; i < n; i++) {
      cnt[i] = temp / list[i];
      temp = temp % list[i];
      if (temp == 0) break;
    }
    System.out.println(Arrays.stream(cnt).sum());
  }
}

 

2차 작성 코드 ✍️

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

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Integer[] list = new Integer[n];
    for (int i = 0; i < n; i++) list[i] = sc.nextInt();
    int total = sc.nextInt();
    int[] result = new int[total + 1];
    Arrays.fill(result, Integer.MAX_VALUE);
    result[0] = 0;

    for (int i = 0; i < n; i++) {
      for (int j = list[i]; j <= total; j++) {
        result[j] = Math.min(result[j], result[j - list[i]] + 1);
      }
    }
    System.out.println(result[total]);
  }
}