[ BAEKJOON ] No. 11047 동전 0

문제 )

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

[ 풀이 ]

동전의 가치가 큰 것부터 사용해야하기 때문에, 그 순간에 가장 좋다고 생각되는 것을 solution으로 선택하는 Greedy Algorithm을 사용하여 문제를 해결하였다. 

 

✔ Greedy Algorithm을 사용하여 풀어준다. 

< Greedy Algorithm이란? > 

결정을 해 야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 solution으로 선택함으로써  
최종 solution에 도달하는 Algorithm이다. 
그 당시에는 최적의 solution을 선택하나 최종적인 solution이 최적이라는 보장이 없다.  
보통 greedy choice property 와 optimal substructure property를 만족할때 사용하는 것이 좋다

 

< mincoin함수의 Algorithm >

✔ coin의 종류 list → arr
✔ 만들어야 하는 가치 → price
✔ coin의 종류 list(arr)에 접근하는 변수 → i  
      ( list의 끝부터 하나씩 접근 )
✔ 사용하는 코인의 갯수 → count 

1. price가 0보다 클때까지 계속 반복
         1-1)
         If price값에서 동전의 값을 빼는것이 가능하다면 
                Ⅰ. price값을 동전값으로 나눈 몫을 구한다 ( 몫 : 동전을 몇개까지 사용할 수 있는지)
                Ⅱ. 동전 갯수에 몫을 더해준다
                Ⅲ. price에서 현재 동전 i를 가지고 지불 할 수 있는 최대금액을 빼준다
                (  price - 동전 i의 값*몫 )

 

 

- python code

def mincoin(arr,price):
    i=len(arr)-1
    count=0
    while price>0:
        if price-arr[i]>=0:
            q=(price//arr[i]) # price값을 동전값으로 나눈 몫
            count+=q
            price-=(arr[i]*q) # price - 동전 i의 값*몫
        i-=1
    return count
            
# Data input
N,K=map(int, input().split())
coinlist=[]
for i in range(N):
    coin=int(input())
    coinlist.append(coin)
print(mincoin(coinlist,K))