[백준 11047] 동전 0 해설 및 풀이 (파이썬)

백준 알고리즘 11047번 | 동전 0

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

---

문제

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

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄의 동전의 가치가 오름차순으로 주어진다.

 

출력

첫째 줄 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

예제 입력 1

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

 

예제 출력 1

6

 

 

예제 입력 2

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 2

12

---

해설

 

거스름돈 문제는 그리디 알고리즘의 예제로 자주 사용되는 문제입니다.

이 문제는 입력으로 들어온 동전들을 사용하여 K원을 만드는데 필요한 동전 개수의 최솟값을 출력하는 것이 목적입니다.

 

 

예제 1로 해설하겠습니다.

예제 1의 입력

다음과 같이 첫번째 줄에는 N(동전들의 종류), K(만들어야 할 값)입니다.

그 아래는 N가지의 동전들이 오름차순으로 입력됩니다.

for range 반복문으로 입력 받아 리스트 형태로 만들어주겠습니다.

그 후 처리의 편의를 위해 역순(내림차순)으로 정렬하겠습니다.

동전 리스트는 coins로 명명하겠습니다.

입력 받은 후에 필요한 정보는 K(만들어야 할 값)와 coins(동전 리스트)입니다.

N은 더이상 필요하지 않습니다.

 

 

우리가 반환해야 할 값은 coins를 사용하여 K원을 만드는데 필요한 동전 개수의 최솟값입니다.

이 최솟값이 바로 답이기 때문에 answer이라는 변수명으로 정하겠습니다.

 

 

저는 answer(K원을 만드는데 필요한 동전 개수의 최솟값)을 구하기 위해서 다음과 같은 방법을 사용했습니다.

 

먼저, coins안에 있는 수 중 K를 나눌 수 있는 가장 큰 수를 찾습니다. 이 예제에서는 1000이네요!

 

그 후 K를 coin(1000)로 나눕니다.

몫은 answer에 더해주고, 나머지는 K에 부여합니다.

 

계산 식은 다음과 같습니다.

answer += K // coin  # 몫만큼 더하기
K %= coin  # 나머지 부여

연산자에 대한 이해가 없으면 이해하기 힘듭니다.

연산자는 이곳을 클릭해서 공부하실 수 있습니다.

 

위 식을 풀어서 쓰면

answer에 K를 coin으로 나누고 나온 몫을 부여합니다.

4200 = 1000 + 1000 + 1000 + 1000 + 200

여기서는 몫은 4네요, 나머지는 200이구요

 

이제 answer에 몫을 더하고,

answer(0) += 4

 

K에는 나머지 값을 부여합니다.

K = 200

 

위 작업을 K가 0이 될때까지 반복해야 합니다.

answer += K // coin  # 몫만큼 더하기
K %= coin  # 나머지 부여

이 작업을 진행하면 K는 0이 되고, answer는 6이 됩니다.

0은 더이상 나눌 수없으므로 반복문을 탈출합니다.

 

이렇게 되서 answer(K원을 만드는데 필요한 동전 개수의 최솟값)은 6이 됩니다.

 

 

다음은 해당 문제를 푸는 코드입니다.

# 1. 계산대 안에 있는 돈의 수와 거슬러 줄 돈을 구합니다.
N, K = map(int, input().split()) # N : 화폐 종류수, K : 거슬러 줄 돈

# 2. 계산대에 있는 화폐들을 리스트의 형태로 입력받습니다.
coins = []
for _ in range(N):
    coins.append(int(input()))
coins.sort(reverse=True)
# coins = [50000, 10000, 5000, 1000, 500, 100, 50, 10, 5, 1]

# 3. 만약 '계산대 안에 있는 화폐'보다 '거슬러 줄 돈'이 크다면
# 돈을 거슬러 줍니다.
answer = 0
for coin in coins:
    if K >= coin:
        answer += K // coin 몫만큼 더하기
        K %= coin 나머지 할당
        if K <= 0: # 만약 K가 0이면 반복문을 탈출합니다.
       		break
print(answer) # 거슬러 준 동전 + 화폐의 수