백준|11047번|동전

문제설명
동전의 종류와 금액을 입력받아서 입력받은 금액을 만들수 있는 동전의 최소개수를 구하는 문제입니다.

작동 순서
1.동전의 종류 개수와 금액을 입력받는다.
2.동전의 종류들을 입력받는다.
3.최대한 금액이 큰 동전부터 이용해서 입력받은 금액을 채워간다.
4.입력받은 금액이 모두 충족되면 사용한 동전의 개수를 출력한다.

소스코드

amount=[]
count=0
quantity, price=map(int,input().split())
for i in range(quantity):
    amount.append(int(input()))
num=quantity-1
while price>0:
    if price>=amount[num]:
        count+=price//amount[num]
        price-=(price//amount[num])*amount[num]
    num-=1
print(count)

후기
간단한 그리디 알고리즘이지만 시간제한이 있었기때문에 어려웠던것 같습니다. 답을 구하는것 자체는 매우 쉬웠지만 반복문의 사용방법이나 동전의 개수를 구하는 방식에서 시간을 많이 소모하는 방식을 사용하였고 이를 최소한으로 줄이기위해서 여러가지 방법들을 사용하다보니 문제를 풀 수 있었습니다.