Greedy Method

greedy-method.py

임의의 동전 셋 coin_set = { 1, 5, 10 } 에서 12를 만들기 위한 가장 적은 동전수는?

3

임의의 동전 셋 coin_set = { 1, 6, 10 } 에서 12를 만들기 위한 가장 적은 동전수는?

3

이와 같이 욕심쟁이 방법을 취할 경우 2번째의 2개라는 더 적은 해가 있음에도 불구하고 10을 선택하는 문제점이 있다

하지만, 구현은 아주 간단하다 단, 아래에서와 같이 coin_set 이 항상 역으로 sort 되어 있어야만 한다

1.   1 #!/usr/bin/python
     2 coin_string = raw_input("coin set? ").split(' ')
     3 coin_set = []
     4 for str in coin_string:
     5     coin_set.append(int(str))
     6 N = int(raw_input("N? "))
     7 coin_set.sort(reverse=True)
     8 count = 0
     9 for co in coin_set:
    10     while co <= N:
    11         count += 1
    12         N = N - co
    13 print count