benji1215   1년 전

그리디 알고리즘은 처음 해보는데

피드백 좀 해주세요

firebird   1년 전

현재 구현하신 코드는 목표금액에서 매번 동전에 해당하는 금액을 찾고, 빼고 있습니다.

이런 경우, 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년 전

이런 효율적인 방법이 있었네요 정말 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.