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

그리디 알고리즘

뒤에서부터 K값보다 그 가치가 크면 계속 반복문 돌고 그렇지 않으면 몫을 계산하여 count에 증가시켜주고 cnt * value[i] 만큼 K에서 빼줍니다.

package greedy;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main11047_동전 {
    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[] value = new int[N];
        for (int i = 0; i < N; i++) {
            int Ai = Integer.parseInt(br.readLine());
            value[i] = Ai;
        }
        
        int count = 0;
        for (int i = value.length-1; i >=0; i--) {
            if(value[i] > K) continue;
            else {
                int cnt = K / value[i];;
                count += cnt; 
                K = K - (cnt * value[i]);
            }
            
            if(K ==0) {
                break;
            }
        }
        
        System.out.println(count);
    }//end of main
}//end of class