[코딩테스트 준비] 동적 프로그래밍 - 거스름돈 주기

문제: 동전의 종류가 들어있는 coins 배열과, 거슬러줘야 할 돈 change을 매개변수로 받아 가장 적은 동전의 갯수로 돈을 거슬러 줘야 한다. 이때, 가장 적은 동전의 갯수를 Return 하라

예시, 1원, 2원, 7원, 10원 동전이 있을때, 14원을 거슬러 줄 수 있는 가장 적은 방법은 7원짜리 2개를 주는 것이다.

---

접근법

위의 예시에서 14원을 거슬러줄 수 있는 방법은 아래와 같다.

14원
1원 동전(1개) + 13원 일 때 갯수
2원 동전(1개) + 12원 일 때 갯수
7원 동전(1개) + 7원 일 때 갯수
10원 동전(1개) + 4원일 때 갯수

이를 봤을떄, 현재 change 에서 각각의 동전의 값을 뺀 값의 갯수 + 1 중에서 가장 작은 값을 return 해주면 된다.

이렇게, 큰 값(14원) 의 갯수 를 작은 값(13원 일때, 12원 일때, 7원 일때, 4원 일때)의 갯수 들로 나누는 것을 동적 프로그래밍 이라고 한다.

동적 프로그래밍 에서는, 작은 값부터 memoization 을 통해 값을 저장을 해주고, 다음 값을 구할 때 쓰면 된다.

현재 알 수 있는 것들은 아래와 같다.

0. 0원 일 때 갯수는 0이고,
1. 각각의 동전의 종류 일 때 갯수는 1이다.
2. 그 외의 값들은 어떤 동전들의 합이 될지 모르기 때문에, 미지의 높은 값 으로 설정 해준다.

dp = [99999999] * (change + 1) # 거스름돈 의 크기만큼 저장
dp[0] = [0]

유의할 점은, dp의 각각의 index는 index원 의 최소 거스름돈 동전 갯수 라는 것이다.
이를 통해, change - 동전의 값을 뺀 값 을 dp에서 찾을 수 있다.

dp[index - coin]

만약 index의 값과 coin이 같은 값을 갖는다면, 각각의 동전의 값을 거슬러줄 때를 칭함으로 dp[0] 이 된다.

이를 이제 코드로 나타내게 되면,

---

코드

def solution(coins, change):
    dp = [999999] * (change + 1)
    dp[0] = 0
    
    for i in range(len(coins)):
    	for j in range(1, change): # 0일때는 0인 것을 알기 때문에 거스름돈이 1원 일 때부터 검사
        	dp[j] = min(dp[j], dp[j - coins[i]]) # 코인의 종류가 바뀔 때마다 dp[j] 에 저장이되고,
            					     # 최종적으로 최솟값을 저장해야기 때문에 min() 으로 비교를 한다.
                                          
    return  dp[change]