Backjoon 11047번 동전 0

백준 알고리즘

• 11047번 동전 0

---

파이썬을 사용하였습니다.
단계별로 풀어보기 그리디 알고리즘 첫번째 단계에 있는 문제입니다.

---

• 입력
  1. 첫줄에 N개의 동전종류와 금액 M이 주어집니다.
  2. N개의 동전종류의 가치가 주어집니다.
  3. 동전을 사용한 최소 갯수를 출력합니다.

---

간단하게 풀수있는 문제입니다. 동전을 가장 적게 사용하려면 비싼가치를 가진 동전을 최대한 많이 써야 합니다.
최대한 비싼 동전을 많이 쓰는 방법으로 생각하면 문제가 쉽게 풀립니다.

간단하게 설명하면 일단 동전의 가치를 하나의 리스트로 저장합니다. (money = [5,10,50,100,500,1000,5000,10000,50000])
이제 주어진 M 즉 금액이 0이 될때 까지 반복문을 돌게 됩니다. (저는 K로 주었습니다)

money 리스트의 가장 뒷부분 즉 가장 비싼 동전을 가져오고 K와 비교합니다. K가 money의 마지막 부분 보다 크면 일단 뺄 수 있는 만큼 뻅니다

(ex k= 102000 일때 50000짜리 동전 두개를 사용할 수 있음) 사용된 동전의 갯수를 answer에 누적하고 반복문을 진행합니다.
이런식으로 조건문을 포함해서 반복문을 돌다보면 결국 우리가 원하는 답을 찾을수 있습니다.

---

정답 코드

n,k = map(int,input().split(' '))
money=[]
answer=0
for i in range(n):
    money.append(int(input()))

while k>=0:
    if len(money)==0:
        break
    mon= money.pop()
    if mon <= k:
        answer += k // mon
        k = k - (k // mon)*mon

print(answer)