Java : 동전 교환(DFS)

문제

풀이

• 금액의 합을 담을 sum
• 최소 횟수를 담을 minCount
• 동전의 가격을 담을 coinArr배열을 만든다.

    if (sum != 0) {
      if (sum > m || l + 1 >= minCount) return;
      if (m == sum) {
        minCount = l;
        return;
      }
    }

• sum != 0 은 아무 동전도 쓰지 않을 경우 m을 절대 초과하지 않아 추가했다.
• 같은 동전의 값을 계속 더하면서 m을 초과하는지 확인한다.
• 합이 m 보다 높거나 최소 횟수보다 l+1이 높으면 다음 동전으로 넘어간다.(return)
  - l+1 은 어차피 동전을 추가해도 최소 값보다 같거나 크기 때문이다.
• 합과 m이 같으면 최소 횟수를 바꿔주고 다음 동전으로 넘어간다.(return)

전체 코드

package inflearn;

import java.util.Scanner;

public class I0805 {
  static int sum = 0, m;
  static Integer[] coinArr;
  static int minCount = Integer.MAX_VALUE;

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    coinArr = new Integer[n];
    for (int i = n - 1; i >= 0; i--) {
      coinArr[i] = sc.nextInt();
    }
    m = sc.nextInt();
    int l = 0;

    dfs(l, 0, sum);
    System.out.println(minCount);
  }

  static void dfs(int l, int idx, int sum) {

    if (sum != 0) {
      if (sum > m || l + 1 >= minCount) return;
      if (m == sum) {
        minCount = l;
        return;
      }
    }

    if (idx == coinArr.length) return;
    dfs(l + 1, idx, sum + coinArr[idx]);
    dfs(l, idx + 1, sum);
  }
}