BOJ / Greedy / 동전 0 / Python

백준 11047번 : 동전 0

내 코드1

n, k = map(int, input().split())
coins = []
ans = 0

for _ in range(n):
    coins.append(int(input()))

coins.sort(reverse=True)

for coin in coins:
    ans += k // coin
    k %= coin

print(ans)

우선 돈이 이상하게 남아버리는 경우는 없다는 걸 알고 있기 때문에 몫과 나머지만을 이용한다.

수정할 것

• k 보다 큰 동전의 경우 애초에 리스트에 넣지 않기
• .sort() 함수 쓸 필요없이 coins[-1] 이용하기

내 코드2

n, k = map(int, input().split())
coins = []
ans = 0

for _ in range(n):
    num = int(input())
    # k보다 작은 수일 경우 리스트에 넣기
    if num <= k:
        coins.append(num)

while k != 0:
	# coins[-1] 이용
    ans += k // coins[-1]
    k = k % coins[-1]
    # 마지막 값 pop
    coins.pop()

print(ans)

실행시간이 줄었다 !