[백준] 11047번 파이썬 - 그리디

문제요약 (11047. 동전 0)

원하는 돈의 가치를 만들기 위해 필요한 동전의 최소 갯수를 구해 출력하라

다양한 경우의 수가 있지만 최소 갯수를 구해야한다.

 

11047번: 동전 0

 

 

풀이를 위한 개념

• 그리디에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다.

 

[코테 알고리즘] DFS, BFS / 관련 문제

 

코드 

import sys
input = sys.stdin.readline

type, price = map(int, input().split())
coinPrice = []

for _ in range(type):
    coinPrice.append(int(input()))

cnt = 0

for i in range(type):
    money = coinPrice[type - i - 1]
    if price % money >= 0:
        cnt += price // money
        price %= money

print(cnt)