[lecture] 5주차.동적계획알고리즘_동전 거스름돈 문제

수업을 듣고 정리한 내용입니다.

동전 거스름돈 문제는 그리디 알고리즘으로 안 풀리는 경우가 있는데, 이때 동적계획 알고리즘은 항상 최적해를 구할 수 있게 해줍니다. 

부분 문제

동전 거스름돈 문제에서의 부분 문제를 정의하기 위해 먼저 문제에 주어진 요소인 1. 동전의 종류 2. 거스름돈 에 대해 정리해본다.

동전의 종류를 d1, d2, ... dk 등으로 정하는 경우 d1 > d2 > ... > dk = 1을 만족해야 한다.

거스름돈은 n원이라고 둔다. 

배낭 문제의 DP 알고리즘에서는 배낭의 용량을 1kg씩 증가시켜가며 문제를 해결하게 되는데, 이때 1원씩 증가시키고, 거스름돈을 배낭의 용량과 같이 생각해본다면 해결된다.

//DPCoinChange
입력 : 거스름돈 n원, k개의 동전의 액면, d1 > d2 > ... > dk = 1
출력 : C[n]
for i=1 to n	C[i] = 무한대
C[0] = 0
for j=1 to n	//j는 1원부터 증가하는 (임시) 거스름돈 액수
	for i=1 to k
    	if(di >= j) and (C[j - di] + 1 < C[j])
        	c[j] = C[j-di] + 1
return C[n]

1번과 2번 라인을 통해 배열을 초기화 한다.

시간 복잡도

거스름돈 j가 1 ~ n 원으로 변하며, 각각의 j에 대해 최대 모든 동전(d1,d2...,dk)(k개)을 1번씩 고려한다. 따라서 시간 복잡도는 O(nk)이다.