psychobabo   9달 전

전체 동전을 배열로 구성해서 (ex, long coins[] = {1,10, 25, 100, 1000, 2500, 10000, ....}

정렬한 후, 아래 소스와 같이 탐욕법으로 구성해 봤는데 자꾸 틀렸습니다가 나오네요..


제가 검토하지 못한 테스트 케이스가 있는걸까요? 아니면 문제를 제대로 이해 못한걸까요?

indioindio   9달 전

25가 10의 배수가 아니어서 무조건 적용하기에는 어렵지 않을까 싶네요.

amugeona   9달 전

작성자님의 방법대로면 34 가 반례가 생깁니다. 34는 10 * 3 + 1 * 4 로 7개를 쓰면 되는데, 25 * 1 + 1 * 9 를 쓰게 되면 10개를 써야합니다.

이런 경우도 잘 처리할 수 있도록 탐욕 알고리즘을 사용하시면 됩니다. :)

psychobabo   9달 전

아 그렇군요! 반례 감사합니다~~ 한번 더 짜봐야겠어요 ^^

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