[백준 - 11047] 동전 0 .java

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

 

 

문제 분석

전형적인 그리디 알고리즘을 이용하는 문제이다

동전을 최소로 사용하여 k 금액을 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다

• K >= 동전금액 -> k / 동전금액 -> 몫은 동전 개수에 추가 , 나머지(k%동전금액) -> k 값으로 갱신

 

 

import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        // 입력 받아 저장
        int n = sc.nextInt();
        int k = sc.nextInt();

        //초기화 및 한줄씩 저장
       int[] coins = new int[n];
       for (int i = 0; i < n; i++) {
           coins[i] = sc.nextInt();
       }
       int count = 0;
        //개수 최솟값 -> 역순
       for(int i = n-1; i>=0; i--) {
           //k가 현재 동전 값보다 크거나 같으면 
           if(k >= coins[i]){
               //동전 개수는 몫
               count += (k / coins[i]);
               //나머지는 갱신해서 다시 계산
               k %= coins[i];
           }
       }

       System.out.println(count);

    }

}