[백준/파이썬] 11047 : 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

문제 요약 : N개의 종류의 동전이 주어졌을때 K원을 만드는데 필요한 동전 개수의 최솟값

 

그리디 알고리즘은 당장 지금 좋은 것만 선택하는 알고리즘이다.

이 문제의 경우 그리디 알고리즘을 적용할 수 있었다. 그 이유는 큰 동전이 전부 작은 동전의 배수가 되기 때문이다.

 

시도 1 )

while문을 이용하여 k가 0이 되기전까지 돌린다.

동전의 종류를 pop()하면 큰 순으로 나오게 되고, 그 값이 k 값보다 작을 때 까지 while문을 돌리면서 k값에다가 a.pop() 한값을 빼주고, ans에는 1을 더해준다.

n,k = map(int,input().split())
a = list(int(input()) for _ in range(n))
ans = 0

while k!=0:
    tmp = a.pop()
    while tmp <= k :
        k -= tmp
        ans += 1
        
print(ans)

테스트 케이스는 다 돌아갔으나 시간초과가 떴다 당연함 쓸데없이 while문을 두번돌렸다.

 

시도 2 )

안에 있는 while문은 굳이 돌릴필요없이, 나머지값과 몫을 이용하면 된다.

n,k = map(int,input().split())
a = list(int(input()) for _ in range(n))
ans = 0

while k!=0:
    tmp = a.pop()
    if tmp <= k :
        ans += (k//tmp)
        k = k%tmp
        
print(ans)