[Python/코테] 다이나믹 프로그래밍(3) - 예제: 효율적인 화폐 구성

3. 효율적인 화폐 구성

 

* Solution:

시간 복잡도: $O(N*M)$

n, m = map(int, input().split())

array = [] # 화펴 단위를 저장할 리스트 변수

# n개의 화폐 단위 정보 입력받기
for i in range(n):
    array.append(int(input()))

d = [10001] * (m+1)  # 1001은 무한을 의미하여, 특정 금액을 만들 수 있는 구성이 불가능하다는 뜻

d[0] = 0			# dp 테이블인 d 의 인덱스는 만들 수 있는 금액, 값은 필요한 화폐 갯수이다.
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)

if d[m] == 10001:  # 만들 방법이 없을 경우
    print(-1)
else:
    print(d[m])

코드 만으로는 이해가 잘 안되어서, 해설에서 제공한 표를 가지고 이해해보았다.

array 배열은 사용 가능한 단위 화폐의 값을 저장하고, d 배열(dp 테이블)의 인덱스는 만들 수 있는 값, 값은 필요한 화폐 단위 갯수를 저장한다.

입력된 단위 화폐를 하나씩 가지고 dp 테이블을 순회하면서 검사하게 된다. 단위 화폐가 커질수록 (뒷 순서 일수록) dp 테이블의 값도 갱신될 수 있는 것.

 

* 나다어

• DP 테이블의 값이 곧 출력해야 하는 결과 값이 된다. 기준을 잡고인덱스나 다른 배열을 활용할 방법을 생각해보자
• 점화식 만들기에 집중하자. 떠올린 하나의 점화식으로 여러 경우를 커버하려고 하기 보다, 단순한 경우의 점화식을 여러개 만들어서 비교하던가 .. 하자.

 

시간 복잡도: $O(N*M)$