[백준][11047번:동전 0]

문제

문제링크
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

코드

import java.util.Scanner;
import java.util.Collections;
import java.util.ArrayList;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int result = sc.nextInt();
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i=0; i<N; i++){
            arr.add(sc.nextInt());
        }
        Collections.reverse(arr);// 배열 거꾸로 뒤집기
        int count=0; //동전 개수
        for(int i=0; i<N; i++){
            if(arr.get(i)<=result){
                count += result/arr.get(i); // 동전개수 
                result = result%arr.get(i); // 사용후 남은 돈
            }
            if(result==0) break; // 돈을 맞췄으니 종료
        }
        System.out.println(count); //결과 출력
    }
}

알고 넘어가야할 것

Collections.reverse() 배열을 거꾸로 뒤집는 함수이다.
입력에서 오름차순으로 값이 주어지기 때문에 거꾸로 뒤집으면 내림차순으로 바뀐다.
내림차순 : Collections.sort(배열,reverseOrder());
오름차순 : Collections.sort(배열);
조건이 없으면 오름차순 reverseOreder()조건이 있으면 내림차순