boj11047 동전0_java

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

나의 풀이

• 동전 개수의 최솟값이므로, 가능한 가장 큰 숫자의 동전의 가장 최대 갯수부터 구하는 방식을 채택하였다. DP보다는 그리디에 가까운 풀이가 될것 같다.
• 재귀를 돌다가 원하는 값이 나오면 return하고, break 하여 for문을 빠져나오는 것으로 로직을 작성하였다.
• 핵심 코드

  private static void getCoins(int[] coinCnt,int value,int index){
          if(value==K){
              answer = Arrays.stream(coinCnt).sum();
              return;
          }
  
          while((K-value)<coins[index]){
              index-=1;
          }
          for (int i = (int) ((K - value) / coins[index]); i >= 0; i--) {
              coinCnt[index] = i;
              value += coins[index] * i;
              getCoins(coinCnt, value, index - 1);
              break;
          }
      }

• 전체 코드

  package Baekjoon.java.silver;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  
  //동전 0
  public class boj11047 {
      static int K,coins[],coinCnt[],answer;
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
  
          int N = Integer.parseInt(st.nextToken());
          K = Integer.parseInt(st.nextToken());
          coins = new int[N];
          coinCnt = new int[N];
          for (int i = 0; i < N; i++) {
              coins[i] = Integer.parseInt(br.readLine());
          }
  
          getCoins(coinCnt,0,N-1);
          System.out.println(answer);
      }
  
      private static void getCoins(int[] coinCnt,int value,int index){
          if(value==K){
              answer = Arrays.stream(coinCnt).sum();
              return;
          }
  
          while((K-value)<coins[index]){
              index-=1;
          }
          for (int i = (int) ((K - value) / coins[index]); i >= 0; i--) {
              coinCnt[index] = i;
              value += coins[index] * i;
              getCoins(coinCnt, value, index - 1);
              break;
          }
      }
  }

결과