이것저것 개발 블로그

https://www.acmicpc.net/problem/11047

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BJ_11047_동전0 {
    public static void main(String[] args) throws Exception{
        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());
        int[] coin = new int[n];
        for(int i=0; i<n; i++){
            coin[i] = Integer.parseInt(br.readLine());
        }

        int cnt = 0;
        for(int i=n-1; i>=0; i--){
            if(k == 0)
                break;

            if(coin[i] > k)
                continue;

            cnt += k / coin[i];
            k = k % coin[i];
        }
        System.out.println(cnt);
    }//main
}

입력에서 친절하게 오름차순으로 제공되어 있으므로 뒤에서부터 확인하면 된다.

k값 보다 같거나 작은 동전 순서대로 k를 동전으로 나눈 몫은 동전 개수, 나머지로 k가 갱신된다.

이 과정을 k가 0이 될 때까지 반복한다면, 답을 쉽게 구할 수 있다!