[백준] 동전 0(11047)

https://www.acmicpc.net/problem/11047

그리디 알고리즘 하면 가장 쉬운 예시로 나오는 동전 문제이다.

그리디 알고리즘이란 이름 그대로 문제가 주어진 조건에서 항상 최선이라고 생각하는 해를 고르는 것이다.

문제에서는 동전을 최소한으로 사용하면서 K의 수를 만들고자 한다.

동전이 $A_1$의 배수 형태로 주어지므로 그리디 알고리즘을 적용할 수 있다.
(만약 배수가 아니라면 그리디를 사용할 수 없으며, DP 알고리즘을 통해 해결해야한다.)

예제 입력1 을 기준으로 생각해보자.
K = 4200을 만들기 위해 동전을 최소한 사용해야 하므로 1000원 x 4, 200 x 2인 총 6개의 동전이 필요하다.

그러면 우리가 코드로 작성할 때는 어떻게 해야할까?

가장 큰 수부터 역으로 조건검사를 하며 4200보다 클 경우 패스하고, 4200보다 작거나 같다면 해당 금액만큼 빼주면서 값을 카운트하면 된다.

if (A[i] > K)
	continue;

while (true) {
	if (A[i] > K) {
    	break;
    }
    K -= A[i];
    count++;
}

아니면 아래와 같이 나머지 연산을 통해 필요한 특정 동전의 개수를 while문 없이 한꺼번에 계산해도 된다.

if (A[i] <= K) {
	count += (K / A[i]); // 사용한 동전의 개수 카운트
    K = K % A[i]; // 사용하고 남은 금액에 대한 환산
}

해당 과정을 금액이 가장 적은 동전까지 반복하면 된다.
따라서 전체 코드는 다음과 같다.

import java.util.*;
import java.io.*;

public class P_11047 {
    public static void main(String[] args) throws IOException {
        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[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }

        int count = 0;
        for (int i = N - 1; i >= 0; i--) {
            if (A[i] > K)
                continue;

            while (true) {
                if (A[i] > K) {
                    break;
                }
                K -= A[i];
                count++;
            }
        }
        System.out.println(count);
    }
}