[baekjoon] 백준 11047번(파이썬): 동전 0

문제

11047번: 동전 0

- 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

- 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다.

- 이때 필요한 동전 개수의 최솟값을 구하는 문제이다.

-  N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

- 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

알고리즘

- 동전이 몇 종류 있는지와 가치의 합을 입력받는다.

- 동전의 가치를 반복문을 통해 입력받아 리스트 변수에 넣는다.

- 동전의 가치를 큰 값부터 비교하기 위해 내림차순으로 정렬한다.

- 동전이 동전의 가치보다 작으면 동전으로 동전의 가치를 나누고 나눈 몫을 변수에 넣는다.

- 나눈 몫은 동전을 곱하고 동전의 가치에서 빼준다.

- 이때 동전의 몫은 동전의 개수가 되기 때문에 동전의 개수를 더해준다.

- 위 과정을 반복하여 동전의 가치가 0이 될 때 멈춰준다.

코드

n, k = map(int, input().split())
coin = [int(input()) for _ in range(n)]
# 동전을 내림차순으로 정렬한다.
coin.sort(reverse=True)
# 동전 개수
count = 0

for i in range(len(coin)):
    # 동전이 K보다 작거나 같으면
    if coin[i] <= k:
        # 동전으로 K를 나눈 몫을 num에 넣는다.
        # 여기서 num(몫)은 개수가 된다.
        num = k // coin[i]
        # num과 동전을 곱해준 값을 k에 빼준다.
        k -= num * coin[i]
        # 개수를 더해준다.
        count += num
    # 가치가 0이 되면 반복문을 멈춰준다.
    if k == 0:
        break

print(count)

github

junjange/CodingTest