Today's Algorithm(2019-03-14)

baekjoon11047. 동전0

이 문제는 탐욕법의 문제의 첫걸음에 해당하는 문제인데요. 정말 탐욕법스럽게만 풀면됩니다. 그럼 탐욕법이란 뭘까요?

탐욕법은 뒤까지 모두 고려하지 않고 각 단계에서 최선의 선택을 하는 방법입니다.

이 문제에서 탐욕법스럽게 푸는 방법은 잔돈에서 낼 수 있는 가장 큰 단위의 동전부터 내는 것입니다. 즉 4400원이 있다면 낼 수 있는 가장 큰 범위인 1000원 단위부터 낸다는 것입니다(1, 5, 10, 50, 100, 500, 1000, 5000 단위 가정)

그럼 모든 잔돈 문제가 이렇게 단순하게 접근 가능할까요? 그건 아닙니다. 왜냐하면 동전 단위에 따라 이렇게 풀 수 없는 경우가 있기 때문입니다. 예를들어 1060원의 잔돈이 있고 10, 50, 100, 530, 1000 단위의 돈이 있다고 생각해봅시다. 이 경우엔 탐욕법스럽게 풀면 1000 * 1개, 50 * 1개, 10 * 1개로 총 3개의 동전이 필요합니다. 하지만 사실 530 * 2개로 해결할 수 있거든요. 물론 이런 동전 단위는 없지만 이러한 경우가 존재할 수도 있다는 것입니다.

하지만 오늘 문제는 이런 경우는 생각할 필요는 없습니다. 문제의 조건에서 이렇게 명시해놓았기 때문입니다. A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 이런 조건에선 저런 억지 케이스가 발생하지 않거든요. 그래서 다음과 같이 풀 수 있습니다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] arr = toArray(br.readLine());
        int answer = 0;
        int n = arr[0];
        int change = arr[1];
        List<Integer> coins = getCoins(n, br);

        while(change != 0) {
            for (Integer coin : coins) {
                int quotient = change / coin;
                if(quotient > 0) {
                    answer += quotient;
                    change = change % coin;
                    break;
                }
            }
        }

        System.out.println(answer);
    }

    private static List<Integer> getCoins(int n, BufferedReader br) throws IOException {
        List<Integer> coins = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            coins.add(Integer.parseInt(br.readLine()));
        }
        coins.sort(Collections.reverseOrder());
        return coins;
    }

    private static int[] toArray(String readLine) {
        String[] arr = readLine.split(" ");
        return new int[]{Integer.parseInt(arr[0]), Integer.parseInt(arr[1])};
    }
}

결국 핵심은 10~16째 줄일텐데요. 동전 큰 금액부터 넣어서 몫이 0이상이면 계산하게 하는 것입니다. 다음엔 좀 더 어려운 동전 문제를 정리해볼게요!!