백준[JAVA] - 동전 0 (11047)

---

A[i] 가 오름차순으로 나열되어 있다고 했으니 

배열의 인덱스값을 높은곳에서 한개씩 내리면 

K보다 큰수를 제거하면서 순차적으로 내려갈 수 있다

그래서 반복문을 돌리며

K보다 큰 수는 제거하고

K보다 작은 수지만 A[i]값중 가장 큰 수부터 계산을 시작해서 값을 도출할 수 있었다!

 

package S4_Baekjoon;
import java.util.*;

public class Baekjoon11047 {
    public static void main(String[] args){
        // 동전을 적절히 사용해서 합을 K로 만들기
        // N는 동전의 개수
        // K는 동전의 가치
        // A[i] 는 동전의 가치

        //K원을 만드는데 필요한 동전 개수의 최솟값

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] A = new int[N];
        int count = 0;

        for(int i = 0; i < N; i++){
            A[i] = sc.nextInt();
        }

        int i = N-1 ;
        while(K != 0){
            if(A[i] > K){
                i--;
            }else{
                count += K / A[i];
                K = K % A[i];
            }
        }
        System.out.println(count);
    }
}