[백준11047 - Java] 동전 0 Greedy 알고리즘으로 풀

Greedy알고리즘 이란?

🎯최적의 값을 구해야 하는 상황에서 사용된다.

🎯각 단계에서 최적이라고 생각되는 방법으로 값을 반환해 나가는 방식이다.

🎯주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적의 답을 구한 뒤 이를 결합하여 전체 문제의 최적의 값을 구하는 경우 사용한다.

쉽게 말해서 규칙을 파악하고 그 규칙을 메서드화 한 후 반복수행하여 값을 구하는 방식이라고 할 수 있다.

 

위 문제에서 규칙을 파악하기 위해 예시를 봐보자.

 

 

예상해볼 수있는 규칙

1. 4200원보다 큰 숫자는 무시해도 된다.

2. i>=2인 경우에는 A의i번째는 Ai-1의 배수라고 하였다. 각 숫자들은 배수관계라는 것을 알 수있다.

예를 들어 10(A의 3번째)은 5(A의 2번째)의 배수이다.

 

우리는 최소한의 연산을 통해 4200원을 만들어야 한다.

머릿속으로 기계적으로 생각해보자.

1. 가장 큰 돈인 1000원이 4개 있으면 4000원이다. 

2. 나머지 돈은 200원이 남는다.

3. 그 다음 큰돈은 500원이다. 200원보다 크므로 넘어간다.

4. 그 다음 큰돈은 100원이다. 100원이 2개 있으면 200원으로 4200원이 완성된다.

 

위 4단계에서 규칙을 찾아보자.

1. 가장  큰 수를 찾아 주어진 값에서 나눈다. (4200/1000 =4) 4번의 반복을 수행했다.

2. 그럼 200원이 남는다. (4200%1000 =200)

[반복 발생]

3. 200원과 같거나 더 작은 숫자를 가져와 다시 나누고 나머지를 구한다.(200/100=2) 2번의 반복 수행, (200%100=0)

3. 200원이 100원 두개를 추가함으로써 반복이 종료된다.

 

 

[코드로 구현]

package greedy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class GreedyP11047 {
    /*
    * 1. 오름차순으로 주어진 금액중 K원보다 많은 수가 입력될경우 break
    * 2. 최대값을 반복해서 더한 후 목표값에서 나눈다. 반복할때마다 cnt증가
    * 3.  나머지가 있을 경우 그다음 큰값에서 2번을 반복
    * 4. 목표값이 0이 될때까지 수행한다.
    * */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int x = sc.nextInt();
            if(x<=K){
            list.add(x);
            }
        }
        list.sort(Collections.reverseOrder());

        findMinCnt(list,K);
    }

//반복되는 과정을 메서드로 구현
    private static int findMinCnt(List<Integer> list, int k) {
        int cnt =0;
        int idx =0;
        while (k > 0) {

            cnt += k/list.get(idx);
            k = k % list.get(idx);
            System.out.println(cnt);
            System.out.println(k);
            idx ++;
        }

        return cnt;
    }
}