📍 문제 설명
💡 접근
교환가능한 동전 중 최대 동전으로 계속 잔돈 교환해주고 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);
}
}