탐욕 알고리즘

문제414.(탐욕 알고리즘)

탐욕 알고리즘을 이용하여 금액과 화폐가 주어졌을 때

가장 적은 화폐로 지불하시오 !

 

액수입력: 14

화폐단위를 입력하세요: 10   7   1

 

결과:

10원: 1개

7원:    0개

1원:    4개

 

"탐욕 알고리즘이 어떤 알고리즘이냐면, 매 순간마다 최선의 선택하는것 입니다.

 즉, 선택할때마다 가장 좋다고 생각되는 것을 선택해나가며

 최종적인 해답을 구하는 알고리즘 입니다.

 이 알고리즘을 설계할 때 유의할 점은

전체를 고려하는게 아니라 문제를 부분적으로 나누어,

나누어진 문제에 대한 최적의   해답을 구하므로 전체적인 최적의 해가 될 수 있는 경우가 존재합니다. "

 

  최단 거리 알고리즘 구현하기 위해서 필요한 알고리즘이

                "탐욕(greedy) 알고리즘 "

 

사람이라면, 14원을 거슬러줘야 할 경우, 7원짜리 2개를 쓰지만

탐욕알고리즘은 큰 화폐단위부터 쓰면서 차례로 거스름돈을 맞춰간다.

그래서 10원짜리 1개, 1원짜리 4개를 거슬러 준다.

 

 

 

참고 스크립트 :

 

 

 

money = int(input('액수입력 : '))

 

cash_type = [int(x) for x in input('화폐단위를 입력하세요 : ').split(' ')]

 

res = coinGreedy(money,cash_type)

 

for key in res:

 

    print('{0}원 : {1}개'.format(key,res[key]))

 

 

 

 

 

문제415. (탐욕 알고리즘) 아래와 같이 결과가 출력되게하시오

****동전 개수를 최소로 나오게 출력

 

>>> print( greedy() )

          액수를 입력하세요 ~   14

          거스름돈의 종류를 입력하세요 ~   10 7 1

 

결과 :  10원 동전 0개, 7원 동전은 2개, 1원 동전은 0개

 

 

>>> print( greedy() )

          액수를 입력하세요 ~   17

          거스름돈의 종류를 입력하세요 ~   10 7 1

 

결과 :  10원 동전 1개, 7원 동전은 1개, 1원 동전은 0개

 

 

>>> print( greedy() )

          액수를 입력하세요 ~   12

          거스름돈의 종류를 입력하세요 ~   10 4 1

 

결과 :  10원 동전 1개, 4원 동전 0개, 1원 동전 2개

        10원 동전 0개, 4원 동전 3개, 1원 동전 0개

 ======================================================

 

def greedy():

    money=int(input('전액을 입력하세요: '))

    coin=[int(i) for i in (input('화폐단위를 입력: ')).split(',')]

    coin.sort(reverse=True)

   

   

    t=1

    while t>0:

   

        a=money+1 #14

        q=''

       

        for i in range(len(coin)):

            if money%coin[i]!=0:

                q+=str(coin[i])+'원'+':'+'0개,'

               

               

            if money%coin[i]==0:

               

                if a > money//coin[i]: #15>(14//7)=2

                    a=money//coin[i]#a=2

                    #cnt+=1

                    q+=str(coin[i])+'원'+':'+str(a)+'개,'    

               

                if a< money//coin[i]:

                    q+=str(coin[i])+'원'+':'+'0개,'

                       

                   

       

        x=''

        sum=0

       

        for i in range(len(coin)):

            b=money//coin[i]

            money=money-coin[i]*b

            x+=str(coin[i])+'원'+':'+str(b)+'개,' #1+4=5

            sum+=b

       

       

        if a>b:

           

            print(x.rstrip(','))

       

        else:

           

            print(q.rstrip(', '))

       

        t=t-1

 

greedy()