[BOJ][Python]11047번 풀이

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

11047번: 동전 0

n,k = map(int, input().split())
c = [int(input()) for _ in range(n)]
c.append(100000001)
cnt = 0
while k != 0:
    for i in range(n+1):
        if c[i]<=k:
            continue
        else:
            cnt += k//c[i-1]
            k = k%c[i-1]
print(cnt)

해당 문제는 저도 모르게 알고리즘을 봐버리는 바람에 크게 고민을 하지 않았던 문제입니다. k원을 최소 갯수의 동전으로 구현하는 문제인데요. k보다 크지 않은 선에서 최대한 k에 근접한 동전을 선택해야 적은 갯수로 k원을 만들 수 있겠죠. 그래서 저는 동전은 오름차순으로 제공된다고 하니까 c[i]가 k보다 작거나 같을 때는 스킵하고 커졌을 때의 인덱스에서 하나를 뺀 금액을 이용하는 방향으로 짜봤습니다. 다만 이렇게 할 경우 50000원 보다 k가 클 경우 계속 컨티뉴로 무한 반복이 되기 때문에 k의 최대값 보다 큰 숫자를 하나 추가 해줘서 50000을 무조건 사용할 수 있도록 했습니다(for문이 다 돌면 50000을 쓰도록 해줘도 같은 효과를 낼 것 같네요. k가 0이 안됐더라도 어차피 50000보다 작은 경우 몫도 나머지도 영향을 안주니까요. 다만 불필요하게 while 한 번에 두 줄의 코드를 실행하겠지만요).