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

 

import math
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)

 

코드 설명 

먼저, 입력 개수와 계산하려는 값을 map 함수를 이용하여 n, k 변수에 저장한다. 그 후 빈 리스트와 카운트를 위한 변수를 선언하고

n의 수만큼 반복문을 통해 동전의 가치를 입력받고 리스트에 저장한다.

저장된 리스트는 가장 큰 동전의 가치가 맨 뒤에 있으므로 리스트의 뒤부터 판단하여 동전의 가치의 값이, 만드려는 값 보다 적다면 나눗셈 연산을 통하여 그 개수를 cnt 변수에 저장하고 남은 금액은 나머지 연산을 통하여 새로 갱신하여 준다. 남은 금액이 0이 되면 종료한다.

 

Point : 가장 큰 가치를 가진 동전을 우선적으로 최대한 많이 사용하고, 나머지 연산을 통하여 남은 금액 까지 모두 처리하면 쉽게 풀 수
있다.