Dynamic Programming 예제

문제

효율적인 화폐 구성 < 이코테 p.227 >

풀이

다이나믹 프로그래밍의 메모이제이션을 적용해서 풀어보면 된다.

먼저, 최소 몇 개의 화폐를 사용해야 해당 숫자를 만들 수 있을지에 대해 dp테이블을 초기화 시켜준다.

d = [10001] * (m+1)

d[0] = 0

0원은 0개의 화폐로 만들 수 있는 단위이므로 0으로 바꿔준다.

그리고 보텀업 방식으로 dp테이블을 채워주면 된다. 주어진 화폐 단위를 하나하나씩 먼저 살펴보면되는데, 코드는 다음과 같다.

for i in range(n):
  for j in range(array[i], m+1):
    # 이미 방법이 존재하는 경우
    if d[j - array[i]] != 10001:
      d[j] = min(d[j], d[j - array[i]] + 1)

예를 들어, 2, 3, 5인 화폐단위가 있으면 먼저 2의 화폐단위로 주어진 수까지 계산할 수 있는 경우를 계산한다. 그다음은 3, 5가 차례대로 실행되는 방식이다.