Algorithm/[BOJ] - JAVA
[백준] 11047 : 동전 0 JAVA 풀이
Codew
2022. 10. 28. 21:34
동전의 개수를 최소로 하는 방법은 가치가 큰 동전을 최대한 많이 사용하는 것이다.
1. 동전의 가치를 입력받고 ArrayList에 저장함
2. ArrayList를 동전의 가치가 큰 순서대로 정렬함
3. K가 0이 될 때까지 동전의 가치가 큰 것부터 거슬러주고 그 동전의 개수를 카운트함
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
ArrayList<Integer> list = new ArrayList<>();
for(int i=0;i<N;i++) {
list.add(Integer.parseInt(br.readLine()));
}
list.sort((o1, o2)->{
return o2-o1;
});
int cnt = 0;
int idx = 0;
while(K!=0) {
if(list.get(idx)>K) {
idx++;
continue;
}
cnt += K/list.get(idx); // 동전의 개수 추가
K %= list.get(idx); // 거슬러주고 남은 돈으로 업데이트
}
System.out.println(cnt);
}
}