[백준]11047번 동전0 - 그리디

 

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

for i in range(len(a)-1, -1, -1):
    if k < a[i] :
        continue
    cnt = cnt + int(k / a[i])
    k = k % a[i]
    if k == 0:
        break
    
print(cnt)

 

코드 설명

먼저 a 리스트에 이용가능한 동전의 가치를 저장해준다. 가장 큰 가치를 가진 동전을 먼저 사용해야 하므로 반복문을 거꾸로 수행한다.

만약 동전의 가치가 K원보다 크다면 continue를 통해 다음 반복을 수행한다. 그렇지 않다면 카운트에 그 몫을 더해준다. k 는 나머지 연산을 통해 숫자를 갱신해준다. k == 0 이 된다면 반복을 종료한다.

 

Point : 가장 높은 가치의 동전을 먼저 사용해야 하므로 뒤에서 부터 반복을 수행한다.