백준 11047 : 동전0 (Greedy, Python)

문제

11047번: 동전 0

 

 

입력 : n = 동전의 가치, k = 만들어야 할 가치

출력 : 사용한 동전의 개수

 

동전 종류는 k가치보다 큰 경우가 있을 수 있다.

입력받은 동전 종류는 오름차순 정렬이 된채로 입력이 되기 때문에

동전배열 맨 뒤에서부터 가치 계산을 하도록 접근했다.

 

 

풀이

n,k = map(int,input().split())
coin=[0]*n

for i in range(n):
    coin[i]=int(input())

cnt=tmp=0
for i in range(n-1,-1,-1):
    if k>=coin[i] :
        tmp=k//coin[i]
        k-=(tmp*coin[i])
        if tmp==0: cnt+=1
        else: cnt+=tmp

print(cnt)

 

처음엔 그냥 for문 안에 while을 넣었다가 시간초과가 났고

그 다음은 세부조건을 고려하지 않아 오류가 났다... 따흑