[백준] 11047번: 동전 0 - JAVA(자바) / 그리디 알고리즘

 

본 문제는 그리디 알고리즘을 이용한 문제이다.

 

그리디 알고리즘을 간단히 설명하자면  greedy(탐욕)알고리즘이고 매 번의 선택에서 가장 좋아보이는 선택을 하여

적절한 답을 찾아 가는 것이다.

 

장점으로는 근사해를 구하는 속도가 매우 빠르다는 장점이 있다.

 

 

 

 

 

동전 개수가 최솟값이 되는 경우를 만족하려면 주어진 K의 값에 대하여 동전의 가장 큰 가치 순으로 나누어 보아야 한다.

for문을 이용하여 큰 가치부터 K를 나누어야 한다. 그리고 동전의 가치가 K보다는 작아야 하므로 큰 경우는 제외시키도록 한다. 제외 시키고 난 후 가장 큰 가치로 나누어서 몫만큼 동전의 갯수를 나타내는 변수 count를 올려준다. 

for문안에서 나누고 난 나머지를 K값으로 바꾸어 주고 for문이 실행되면서 k가 0이 되면  for문이 종료된다.

 

import java.util.Scanner;

public class b11047 {

    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);
    }

}