BOJ 11047 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

풀이 방법

그리디 탐색법의 가장 기본적인 문제이다. 그리디 알고리즘은 탐욕알고리즘, 욕심쟁이기법 이라고도 한다.매순간 최적이라고 생각하는 해를 선택해 나가서 최종적으로 최적해에 도달하는 알고리즘이라고 할 수 있다.

코드

n,k = map(int, input().split())
lis = [int(input()) for _ in range(n)]
lis2 = [i for i in lis if i<=k]

cnt=0
while 1:
    nmg = k%max(lis2)
    cnt+=k//max(lis2)
  
    if nmg==0:
        print(cnt)
        break
    else:
        k=nmg
        lis2.remove(max(lis2))