동전 0

❓문제

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

❗문제 정리

📑코드

n, k=map(int, input().split())
coins=[]
for i in range(n):
    coins.append(int(input()))
coins.sort(reverse=True)
#큰 수부터 거슬러 주면 주는 동전의 최솟값을 구할 수 있음
count=0#거슬러 주는 코인의 개수
for coin in coins:
    count+=k//coin #0인경우 
    k-=coin*(k//coin)
    if k==0:
        break
print(count)

📝코드 설명

n, k=map(int, input().split())
coins=[]
for i in range(n):
    coins.append(int(input()))

필요한 파라미터 입력받기
n(int) : 동전 종류의 개수
k(int) : 만들고자하는 금액

coins.sort(reverse=True)

큰 수부터 거슬러 주면 주는 동전의 최솟값을 빠르게 구할 수 있다.

count=0
for coin in coins:
    count+=k//coin #0인경우 
    k-=coin*(k//coin)
    if k==0:
        break

count(int) : 거슬러 주는 동전의 수

• 금액이 동전으로 나누어 떨어지는 경우, 몫을 취해서 count로 할당한다.
  e.g) 50000//500=1000
  k=50000, coin=500, count=1000
• 차액을 계산한다. 동전의 개수동전의금액을 전체 금액에서 빼준다.
  e.g) 50000-5001000=0 <- 잔액 0
• 잔액이 0이면 멈춘다.

🎖제출 결과

💡insight

이코테- 그리디 알고리즘