동전교환 - python

<문제>

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종 류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.

 

▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

 

▣ 입력예제 1

3
1 2 5
15

 

▣ 출력예제 1

3

 

<설명>

DP 테이블을 M + 1만큼 만든다 이때 0의 값은 0으로 두고 모든 값들은 1000으로 초기화 한다. 인덱스의 의미는 거스름돈이다.

그 후 2번째 입력값을 리스트L에 저장후  이용해서 DP[j-L[i]] + 1 과 DP[j] 값중에 작은 값을 DP[j] 값에 저장한다.

위 문제로 풀어서 설명하자면, 첫번째 1이니까 DP테이블에 있던 값들과 비교해서 가장 작은 값들을 넣는다(1이니까 그냥 0,1,2,3,4.. 이렇게 됨) 그 후 2가 오면 j-L[i]의 의미는  2로 예를 들면 j-2에 있는 값이 동전을 사용한 최소개수가 저장되어있다 라는 의미 이다. 이 값에  2원의 가치인 코인을 사용하면 + 1 이 되고 그 값을 저장한다.

그렇게 반복문을 돌리고 DP[m] 을 출력하면 답을 구할 수 있다

 

<코드>

n = int(input())
L=list(map(int,input().split()))
m = int(input())
DP=[1000] * (m+1)
DP[0] = 0

for i in range(n):
    for j in range(L[i],m+1):
        DP[j] = min(DP[j-L[i]] + 1,DP[j])
    # print(DP)
print(DP[m])