배수 (1) 썸네일형 리스트형 [코드트리] Greedy - 그리디 알고리즘 / 동전 연습문제 1, 4, 5 동전을 이용하여 8원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 위 문제를 보면 당연히 큰 동전부터 쓰는 것이 좋아 보입니다. 하지만 큰 동전부터 사용하게 되면 5 + 1 + 1 + 1이므로 4개의 동전이 필요하지만, 4 + 4 역시 8 이므로 최소 동전의 수는 2가 됩니다. 그런데 다음 경우는 어떨까요? 1, 5, 10, 20 동전을 이용하여 78원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 이 경우에는 큰 동전부터 거슬러주는 것이 항상 좋습니다. 그 이유는 주어진 동전들이 전부 배수관계에 놓여있기 때문입니다. 그렇기에 큰 동전이 사용이 가능하다면, 작은 동전을 사용하는 것보다 항상 좋은 선택이 되는 것입니다. 따라서 배수 .. 이전 1 다음