현재 구현하신 코드는 목표금액에서 매번 동전에 해당하는 금액을 찾고, 빼고 있습니다.
이런 경우, k값이 매우 크고 주어진 동전 금액이 매우 작은 경우 굉장히 오래 걸릴 수 있습니다.
ex) k=100억(문제의 조건에선 벗어나지만), 동전은 1원짜리만 있는 경우 100억회의 연산이 필요합니다.
따라서 한번에 Ai원 짜리 동전으로 가능한 많이 빼주고, 그다음 Ai-1 동전으로 넘어가는 것이 훨씬 효율적입니다.
ex) k=12345 , 동전은 100,10,1원 인경우,
100원짜리 123개, 잔액 45원
10원짜리 4개, 잔액 5원
1원짜리 5개, 잔액 0원
구현은 / 과 % 연산을 사용하시면 됩니다

benji1215 1년 전 1
그리디 알고리즘은 처음 해보는데
피드백 좀 해주세요