BOJ 11047: 동전 0 - 파이썬(Python)

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

<접근 방법>

가지고 있는 동전 리스트를 기반으로 사용할 수 있는 최소한의 동전 개수를 구하는 문제이다.

 

여기서 고려할 수 있는 정리를 구성해보자.

정리1
모든 $N < M$인 동전 $N, M$에 대해서 고정된 값 $S$에 대하여 $S = N \times a = M \times b$ 이면 $a > b$ 이다.

 

해당 정리의 예시를 살펴보자.

$N = 100, M = 500, S = 1000$이라고 하자. 그러면 아래와 같이 구성할 수 있을 것이다.

$$1000 = 100 \times 10 = N \times 10$$

$$1000 = 500 \times 2 = M \times 2$$

결과적으로, $a = 10, b = 2$가 되고 그러면 $a = 10 > 2 = b$ 가 만족한다.

즉, 더 큰 값으로 먼저 $S$를 구성하는 것이 최솟값을 만들 수 있을 것이다.

 

하지만 모든 동전들에 대해서도 적용이 가능한지는 아직 미지수이다.

해당 정리를 증명해보자.

$pf)$
모든 $N < M$인 동전 $N, M$에 대해서 고정된 값 $S$에 대하여 $S = N \times a = M \times b$ 이지만, $a \le b$인 N, M이 존재한다고 가정하자.

그러면 2가지 경우에 대해 고려하면,

$i)\, a = b$
$N \times a = M \times a$이므로, N = M이여야 한다. 하지만 N < M이므로 모순이다.

$ii)\, a < b$
$N \times a = M \times b$ 를 정리하면 아래의 식을 구성할 수 있다.
$$\frac{a}{b} = \frac{M}{N}$$
여기서, $N < M$이므로, $1<\frac{M}{N}$이다. 따라서, $1<\frac{a}{b}$이 되어야 한다.
그러나, 가정에서 $a < b$이므로, $\frac{a}{b} < 1$이 되어야 한다.
따라서 모순이 발생한다.

즉, $a \le b$인 N, M이 존재하지 않는다.
결과적으로 모든 $N < M$인 동전 $N, M$에 대해서 $S = N \times a = M \times b$ 이면 $a > b$ 이다. $\square$

 

따라서, 가장 큰 동전으로 최대한 값을 처리하고 남은 값을 그 다음으로 큰 동전으로 처리하는 방식을 반복하여 사용하면 된다.

<소스 코드>

위의 접근 방법을 이용한 전체 소스 코드 구현 결과이다.

import sys

coin, cost = map(int, sys.stdin.readline().split())
coins = []

for i in range(coin):
    coins.append(int(sys.stdin.readline()))
count = 0
coins.sort(reverse = True)

for bill in coins:
    while cost >= bill:
        if bill <= cost:
            count += cost // bill
            cost = cost % bill
        elif cost == 0:
            break
print(count)