[BOJ 11047] 동전 0 파이썬 풀이

 

11047번: 동전 0

문제 해설

2019/09/03 - [DEVLOG/Algorithms] - [BOJ 11399] ATM 파이썬(Python) 풀이

[BOJ 11399] ATM 파이썬(Python) 풀이

11047 동전 0 문제는 전에 포스팅했던 ATM 문제와 함께 대표적인 그리디 알고리즘 문제입니다.

그리디 알고리즘(greedy algorithm)이란 미래의 상황을 고려하지 않고, 현재 시점에서 최선의 선택을 하는 알고리즘을 말합니다.

그리디 알고리즘은 최적화된 해를 찾는다는 보장은 없습니다.

 

각 동전의 value는 오름차순으로 정렬되어 입력됩니다.

이를 내림차순으로 차례대로 K값에 각 동전이 몇개 필요한지 계산해나가면됩니다.

 

동전의 값이 K보다 작거나 같은경우에만 리스트에 포함되도록 했습니다.

코드

N, K = map(int, input().split())
value_list = []
for _ in range(N):
    value = int(input())
    if value <= K:
        value_list.append(value)

cnt = 0
for i in range(len(value_list)):
    value = value_list[(len(value_list))-i-1]
    cnt += (K // value)
    K = K%value

print(cnt)

 

좀 더 단순한 코드

n,k=map(int,input().split());c=0
for i in reversed(eval("int(input()),"*n)):c+=k//i;k=k%i
print(c)