백준 11047: 동전 0

아이디어

그리디가 최적해 보장

큰 단위의 동전은 항상 작은 단위의 동전으로 표현할 수 있으므로 그리디 알고리즘이 최적해 보장!

큰 단위의 동전부터 for 루프

coins.reverse()로 큰 단위 부터 루프

나눗셈

동전으로 금액을 나누어 얻은 몪만큼 동전 개수 카운트 증가.

동전으로 금액을 나누어 얻은 나머지가 새로운 금액이 됨.

탈출

새로운 금액이 0이 될 때 이미 답은 나왔지만 for 루프를 계속 돌게 됨.

탈출 조건을 주고 최적화 가능 (둘다 O(n)이므로 성능 차이는 미미하다).

시간 복잡도

coins를 정렬하는데 O(n) (처음부터 내림차순 정렬이 아니라 오름차순을 단순 재배열하므로)

for 루프에서 O(n).

k와는 관계 없음.

최종적으로 O(n)이고 최악의 경우 10이므로 충분히 가능.

코드 구현

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]

coins.reverse()
cnt = 0
    
for coin in coins:
    cnt += (k // coin)
    k %= coin
    if k == 0: break

print(cnt)