[백준 11047] 동전 0 with 파이썬

요구사항

동전을 최소로 사용해서 원하는 금액을 만들어라

 

참고

1. 구현 문제이다

2. 최소 갯 수로 원하는 금액 만들기

-> 큰 액수의 금액을 최대한 사용해야지 최소의 갯 수로 금액을 만들 수 있다

-> 큰 원소부터 탐색하여 타겟 금액을 만들어 보자

풀이

n,m = map(int, input().split())
arr=[int(input()) for i in range(n)]
ans=0

for i in range(n-1,-1,-1):
    #타겟 넘버가 현재보다 크면 현재껄로 빼준다
    #print(arr[i])
    if( m >= arr[i]):
        #몫을 구한다
        
        div_num = m//arr[i]
        #나머지
        mar_num = m%arr[i]
        #몫을 정답에 더한다
        ans+=div_num
        #m업데이트 한다
        m -= (div_num*arr[i]) 
        """print()
        print(arr[i])
        print(div_num)
        print(mar_num)
        print(m)"""

print(ans)