[백준] Q11047 동전(java, 그리디 알고리즘)

그리디 알고리즘의 대표적인 문제, 동전문제를 풀어보았다.

어렵지는 않았다.

 

그리디알고리즘 : 지금 이순간 가장 최적의 값 선택 -> 결론적으로 최적의 값

(교수님은 인생은 그리디 알고리즘이 아니라고 하셨다..)

 

 

import java.util.*;
 
public class Q11047{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
 
        int N = scan.nextInt();
        int target = scan.nextInt();
        int[] mkinds = new int[N];
 
        for(int i=0; i<N; i++){
            mkinds[i] = scan.nextInt();
        }
 
        int cnt = 0;
        for(int i=N-1; i>=0; i--){
            int m_count = target/mkinds[i];
            target -= mkinds[i] * m_count;
            cnt += m_count;
 
            if(target==0)   break;
        }
    System.out.println(cnt);
 
    }
}