[BOJ/그리디] 11047 동전 0

문제 링크 : https://www.acmicpc.net/problem/11047

11047번: 동전 0

---

풀이

n,k = map(int,input().split())

answer = 0
coin_list = []

# n번 반복
for i in range(n):
    coin_list.append(int(input()))

# 순서바꾸기
coin_list = coin_list[::-1]

for j in coin_list:
    if k//j:
        answer += k//j
        k = k%j
    else:
        pass

print(answer)

- 동전의 가치를 역순으로 바꾼 뒤 K원을 나눴을 경우 몫이 0이상이라면 몫 만큼 동전의 개수를 더하고 K는 그 나머지로 갱신한다.

ps. 만약 나머지가 0이라면 반복문을 종료하는 것이 시간복잡도를 줄이는 데 도움이 될 것이다.