[이코테 실전문제] 효율적인 화폐 구성 (다이나믹 프로그래밍)

문제 N가지 종류의 화폐가 있다. 이 화폐들을 최소한으로 사용해 합이 M원이 되도록 하고자 한다.

M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하시오. 조건 입력조건 1.

첫째 줄에 N,M이 주어진다. 2. 이후의 N개 줄에는 각 화폐의 가치가 주어진다.

출력조건 1. 첫째 줄에 최소 화폐 개수를 출력한다. 2.

불가능할 때는 -1을 출력한다. 코드 n,m = list(map(int,input().split())) array=[] for i in range(n): array.append(int(input())) d=[10001]*(m+1) d[0]=0 for i in range(n): for j in range(array[i],m+1): if d[j-array[i]]!

=10001: d.....