[그리디 알고리즘] 11047번 - 동전

[백준] 11047번 - 동전

1) 문제 해결 아이디어

사실상 최소 개수로 동전을 거슬러주는 문제와 동일하다.

 

동전의 가치가 큰 동전을 최대한 많이 거스는 것이 동전을 최소로 하기 위한 방법이다.

동전 종류를 큰 순서대로 내림차순하여 처리하는 것이 포인트다.

높은 금액대부터 for문으로 검사하여 동전 가치가 금액보다 작거나 같으면 몇 개를 바꿀 수 있는지 계산하여 더해주는 방식으로 구현하였다.

 

 

2) 소스코드

n, k = map(int, input().split())  # 동전 종류 수, 총 금액
coins = [int(input()) for _ in range(n)] # 동전 가치(오름차순)
coins.sort(reverse=True)  #  내림차순 정렬
cnt = 0  # 필요한 동전 개수

# 필요한 동전 개수 최솟값 찾기
for coin in coins:
  # 모두 잔액이 처리되면 탈출
  if(k == 0):
    break
  # 동전 가치가 금액보다 작거나 같으면
  if(coin <= k):
    n = (k // coin)  # 동전 종류 k로 바꿀 수 있는 최대 개수 
    k -= (coin * n)  # 잔액 변경
    cnt += n         # 개수 추가

print(cnt)