[Python] 백준 11047: 동전 0

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

11047번: 동전 0

1차 시도

n, k = map(int, input().split())
lis = []
for i in range(n):
    money = int(input())
    lis.append(money)
#입력으로 받은 n개의 돈 단위를 money list에 저장

money_ans = []
s_lis = sorted(lis, reverse=True)

#내림차순으로 정렬(잔돈 최소화 위해)
for j in s_lis:
    cnt = 0
    while k - j >= 0:
        cnt += 1
        k -= j
    money_ans.append(cnt)
#잔돈 계산
print(sum(money_ans))

시간 초과가 나왔다. 아마도 while 문을 줄여야 할 거 같은데...

 

ANS

 

n, k = map(int, input().split())
lis = []
for i in range(n):
    money = int(input())
    lis.append(money)

money_ans = []
s_lis = sorted(lis, reverse=True)

for j in s_lis:
    cnt = 0
    while k // j > 0:
        cnt = (k//j)
        k = k % j
    money_ans.append(cnt)
#빼기로 길어지는 while문 나누기로 한 번에 줄였다. 몫만큼 돈 단위 수를 세고 나머지를 계속 for문에 돌려주면 된다.
print(sum(money_ans))

전형적인 그리디 알고리즘.