[Algorithm] [이코테] 효율적인 화폐 구성 (Feat. 다이나믹 프로그래밍)

다이나믹 프로그래밍 보텀업 방식 이용

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

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

# 한 번 계산된 결과를 저장하기 위한 dp 테이블 초기화
d = [10001] * (m+1)
d[0] = 0

# 다이나믹 프로그래밍 진행 (보텀업)
for i in range(n):
    for j in range(array[i], m+1):
        if d[j - array[i]] != 10001:  # (i-k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j-array[i]]+1)

# 계산된 결과 출력
if d[m] == 10001:  # m원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

적은 금액부터 큰 금액까지 확인하면서 차례대로 만들 수 있는 최소한의 화폐 개수를 d에 저장해둔다.

• aᵢ₋ₖ (= 금액 (i-k)원을 만들 수 있는 최소한의 화폐 개수) 가 존재하는 경우
  • 점화식 : aᵢ = min(aᵢ, aᵢ₋ₖ + 1 )
• aᵢ₋ₖ 만드는 방법이 존재하지 않는 경우
  • aᵢ = 10,001