특정한 종류의 동전이 있다고 했을 때
동전을 최소 개수를 사용하여 거슬러주고자 한다.
이 문제도 DP를 사용하여 풀 수 있다.
문제 정의
- D[i] = i원을 바꾸어주기 위해 필요한 최소 동전의 개수
- 2원, 5원, 9원 세 종류의 동전이 있다.
아래 그림과 같이 i원에 대한 D 배열을 채워보았다.
i=7을 채우기 위해서 다음과 같은 점화식을 사용했다.
D[i] = min(D[i-2]+1, D[i-5]+1, D[i-9]+1)
따라서 7인 경우,
D[7] = min(D[5]+1, D[2]+1, -) = min(2, 2, -) = 2
처음에는 되게 헷갈렸는데, 포인트는 '마지막 동전이 무엇인지' 이다.
마지막 동전이 2원일 경우, 5원일 경우 9원일 경우를 고려해서
앞의 배열의 값들을 활용할 수 있다.
거슬러 줄 돈이 300원인 경우에도 마찬가지로 하면 된다.
D[300] = min(D[300-2]+1, D[300-5]+1, D[300-9]+1)
D[0]부터 시작해서 앞의 값들을 이용하여 DP 배열을 한 번만 채워주면
이후에는 앞에서 있는 값들을 인덱스를 통해 조회만 하면 되니까
모든 경우의 수를 따져보지 않아도 되서 좋은 것 같다.
참고로 적은 동전의 개수를 거슬러주기 위해 가장 큰 단위의 동전인 9원부터 채운 다음 남는 걸 더 작은 단위의 동전으로 채우는 로직은 예외가 있어서 원하는대로 동작하지 않는다.
Game Programmer