문제 내용은 첫 입력으로 들어올 동전 갯수와, 금액을 받고 그 다음에 입력으로 받는 동전들을 활용해서 가장 최소의 동전을 사용해서 0을 만드는 경우, 사용한 동전 개수의 최소값을 구해야 한다.
위 경우의 입출력 예제를 보면 동전 갯수의 최소값은 1000원을 4번, 100원을 2번 사용해서 총 6번의 동전을 사용해서 4200원을 만드는 경우가 최소값이 되겠다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] arr = br.readLine().split(" ");
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < Integer.parseInt(arr[0]); i++) {
list.add(Integer.parseInt(br.readLine()));
}
Collections.reverse(list);
int count = 0;
int makeValue = Integer.parseInt(arr[1]);
for (int i = 0; i < list.size(); i++) {
if (makeValue / list.get(i) > 0) {
count += makeValue / list.get(i);
makeValue -= list.get(i) * (makeValue / list.get(i));
if (makeValue == 0) {
break;
}
}
}
System.out.println(count);
}
}문제를 풀어보자면 일단 Split으로 입력받은 동전 갯수와, 만들어야 하는 금액을 쪼개준 후
for 문을 돌리면서 받은 동전을 모두 넣어주고 작은 값 부터 들어오기 때문에 Collections.reverse() 를 사용해서 list를 큰 수가 가장 먼저 오도록 뒤집어주자.
다음은 for 문을 list의 size만큼 돌려주면서 list의 인덱스 값으로(큰 수부터) 입력받은 잔액을 나눌 수 있는지 확인한 후, 나눌 수 있다면 나누고 값 변경해준 뒤, 나눈 횟수를 더해주는 식으로 계속 돌려주다가, 잔액이 0이 되면 for문 중단하고 지금까지 나눈 횟수를 반환해주면 끝이다.
Leave a Reply