[JAVA] 백준 11047 - 그리디 알고리즘

 

오늘 문제는 그리디 알고리즘이다.

문제를 풀기 전에 그리디 알고리즘(Greedy Algorithm)이 뭘까를 쉽게 알아보고 가자.

 

그리디 알고리즘은 말그대로 탐욕 알고리즘!

최적의 답을 선택하는 과정을 반복하여 적합한 결과를 도출한다는 것이 그리디 알고리즘이다.

즉 큰 틀, 미래를 생각하지 않고 각 단계를 보아 무엇이 최선의 선택일지 판단하고 도출하면 되는 것이다.

 

 

이 문제는 동전 개수의 최솟값을 구하는 프로그램을 작성하고 있다.

여기서 그리디 알고리즘을 적용하면, '최솟값'을 위해서

액수가 큰 가치를 먼저 탐색하면 되는 것이다.

 

익히 본 문제들을 푸는 과정과 비슷해보이지만,

액수가 큰 가치를 먼저 활용하기 위해서 for문을 역순으로 활용하는 정도라고 생각하면 된다.

 

 

 

import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        
        Scanner in = new Scanner(System.in);
        
        int N=in.nextInt();
        int K=in.nextInt();
       
        int[] arr=new int[N];
        
        for(int i=0;i<N;i++){
            arr[i]=in.nextInt();
        }
        
        int count=0;
        
        for(int i=N-1;i>=0;i--){
            if(arr[i]<=K){
                count += (K/arr[i]);
                K=K%arr[i];
            }
        }
        
        System.out.println(count);
        
       
    }
}