25. 금화 모으기, 동전 거스름돈 문제 [11 1주차]

25. 금화 모으기, 동전 거스름돈 문제 [11-1주차]

2024년 1월 14일 일요일

오전 3:10

<금화 모으기 문제>

격자 공간 위에 금화를 모으는 로봇이 있다. 로봇은 좌측 하단에서 출발하여 우측 상단의 칸까지 최단 거리로 이동한다. 따라서 로봇은 오른쪽 또는 위쪽으로만 한 칸씩 이동할 수 있다.

로봇이 위치한 칸에 금화가 있을 경우, 로봇은 금화를 줍는다. 금화를 최대한 많이 모을 수 있는 경로를 찾아라.

Cell(i, j)를 다음과 같이 정의한다.

Cell(i, j) : 로봇이 (i, j)칸에 도착할 때까지 모을 수 있는 최대 금화 개수.

Cell(i, j)에 대한 점화식을 다음과 같이 세울 수 있다.

Cell(i, j) = max {  Cell(i-1, j),  Cell(i, j-1) } + Coin(i, j)

Coin(i, j) : (i, j)칸에 금화가 있으면 1, 없으면 0을 리턴

위 점화식에 따라 각 칸에 Cell(i, j)를 적으면 문제를 풀 수 있다.

<동전 거스름 돈>

N원의 거스름 돈을 돌려 줄 때, 최소 개수의 동전을 사용하여 거스름돈을 돌려주는 방법을 구하시오.

동전의 종류는 1원, 4원, 6원이다.

만약 8원이 입력된다면, 그리디 방법으로 일단 6원을 거슬러 주면(6+1+1) 답(4+4)을 맞출 수 없다.

동적계획법을 이용하여 거스름 돈 문제를 해결해 보자.

C[j]에 j원이 입력되었을 때의 최적해를 저장한다면, 다음과 같은 점화식이 성립한다.

이 점화식을 이용하면 쉽게 재귀 코드를 짤 수 있을 것이다. 그러나 재귀 과정에서 중복이 발생한다.

위 재귀 트리에서 볼 수 있듯이 중복이 많이 발생하므로, 동적계획법을 통해 중복을 막아 보자.

C[0] -> C[1] -> C[2] -> … 순으로 최적해를 계산한다.

배열 C는 위 표와 같이 구성된다.

C[8]을 구하려면, C[7], C[4], C[2]중 가장 저장된 값이 작은 것을 택해 1을 더하면 된다.