[백준] 11047번 동전 0 - Python

문제 

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오

입력

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오

출력

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

예제 입력 1

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

예제 출력 1

6

---

문제 해석 

# 필요한 동전 개수의 최소값 구하기 (거스름돈 문제와 유사)

의사 코드 

# 사용자 입력 받기 (동전의 종류 : N, 동전의 합 : K)
# N번만큼 반복문 돌려서 동전의 가치 저장하기 (얼마를 가지고 있는지 알아야 하니까)
# 동전의 가치(Ai) 역순으로 다시 정렬 (가장 큰 단위부터 사용해야 하니까) ? 뒤에서부터 꺼내는거 스택? 큐? 아닌가..?
# -> 그리디 알고리즘?
# K와 같아지면 함수 종료

 

정답 코드

# 사용자 입력 받기
n, goal = map(int, input().split())

# 동전을 담을 리스트 초기화
coins = []

for _ in range(n):
    coins.append(int(input()))

# 가지고 있는 동전을 내림차순으로 정렬
coins.sort(reverse=True) # -> 그리디 방식으로 풀기 위한 정렬 

# 필요한 동전의 개수를 저장할 변수 초기화
result = 0 

# 가지고 있는 동전을 종류별로 반복 (각 단계에서 가능한 많은 큰 가치의 동전을 사용함으로써 최적의 해를 찾는다.)
for coin in coins:

    # 가지고 있는 코인이 목표보다 작거나 같으면 실행 
    if coin <= goal:
        coin_count = goal // coin # 현재 동전으로 만들 수 있는 최대 개수 계산 
        result = result + coin_count # 필요한 동전의 총 개수를 결과에 저장 
        goal = goal - (coin * coin_count) # 목표 갱신하기 (목표에서 - 현재 가지고 있는 코인과 필요한 코인 갯수 곱해서 빼기)

    # 목표를 더 이상 갱신할 수 없을 때 (-> 갱신한 동전의 합이 0일 떄) 
    if goal == 0:
        break

print(result)

 

이 코드가 그리디 알고리즘인 이유

① 최적의 부분 해 선택:
코드는 매 단계에서 가장 큰 가치의 동전부터 사용한다. coins.sort(reverse=True) 로 동전을 내림차순 정렬하는 부분에서 확인할 수 있다. 또한 각 반복에서 현재 가능한 가장 큰 동전을 최대한 많이 사용한다. 이는 coin_count = goal // coin 부분에서 나타난다. 

② 지역적 최적해를 통한 전역 최적해 도출:
각 단계에서 현재 가능한 최선의 선택(가장 큰 동전 최대한 사용)을 함으로써, 전체적으로 최소 개수의 동전을 사용하는 해답을 찾고자 한다. 

③ 반복적 선택:

for coin in coins: 루프를 통해 각 동전에 대해 위의 과정을 반복한다. 

④ 한 번 선택하면 되돌리지 않음:
한번 선택한 동전은 다시 고려하지 않는다. 목표 금액을 갱신하고 다음 동전으로 넘어간다. 

⑤ 단순하고 빠른 결정:
각 단계에서의 결정(어떤 동전을 얼마나 사용할지)이 매우 단순하고 빠르다.