동전 0

📍 문제 설명

💡 접근

교환가능한 동전 중 최대 동전으로 계속 잔돈 교환해주고 0원이 될 때 카운트 값을 리턴시킨다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public static boolean[] visited = new boolean[9];

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int m = kb.nextInt();
        Integer[] arr = new Integer[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

        Arrays.sort(arr, Collections.reverseOrder());

        //거슬러준 동전의 갯수
        int cnt = 0;
        //현재 동전의 가치
        int i = 0;
        //거슬러줄 수 있는 동전중 제일 큰 동전부터 바꿔준다.
        while(m > 0) {
            //거슬러 줄 수 있으면
            if(arr[i] <= m) {
                m -= arr[i];
                cnt++;
            }
            //없으면 다음 낮은 가치의 동전으로
            else i++;
        }
        System.out.println(cnt);
    }

}