💥이코테 실전문제 뽀개기💥

💻 8-4 효율적인 화폐 구성

난이도🖤🖤🤍 | 풀이시간 30분 | 제한시간 1초 | 메모리제한 128MB

📌2021/02/03 작성 코드

# 효율적인 화폐 구성
n, m = map(int, input().split())
coins = [int(input()) for _ in range(n)]

# 10001, 불가능한 큰 수 설정
dptable = [10001]*10001
# 0원 만들기 위해 필요한 화폐 개수는 0
dptable[0] = 0

for i in range(m+1):
    for coin in coins:
        if 0 <= i-coin:
            dptable[i] = min(dptable[i], dptable[i-coin]+1)

if dptable[m] == 10001:
    print(-1)
else:
    print(dptable[m])

💭 아이디어

• 솔루션이 쉽게 떠오르지 않아서 해설을 먼저 참고하고 혼자 코드를 짰다.

• 혼자 정리해 본 아이디어는 이렇다.
  

🤓 문제 해설

이 문제는 그리디에서 다루었던 거스름돈 문제와 거의 동일하다. 단지 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니라는 점만 다르다. 그렇기 때문에 그리디 알고리즘을 사용했던 예시처럼 매번 가장 큰 화폐 단위부터 처리하는 방법으로는 해결할 수 없고 다이나믹 프로그래밍을 이용해야 한다.

이번 문제는 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다.
금액 i르 만들 수 있는 최소한의 화폐 개수를 ai, 화폐의 단위를 k라고 했을 때 다음과 같이 점화식을 작성할 수 있다. ai-k는 금액(i-k)를 만들 수 있는 최소한의 화폐 개수를 의미힌다.

• ai-k를 만드는 방법이 존재하는 경우, ai = min(ai, ai-k+1)
• ai-k를 만드는 방법이 존재하지 않는 경우, ai = 10,001

이 점화식을 모든 화폐 단위에 대하여 차례대로 적용하면 된다. 실제로 문제를 풀기 위해서는 가장 먼저 k의 크기만큼 리스트를 할당한다. 이후에 각 인덱스를 '금액'으로 고려하여 메모이제이션을 진행한다.

🤓 답안 예시

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
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[j-array[i]]가 10001인지 검사하는 부분은 사실 없어도 되는 코드인데, d[j-array[i]]가 10001의 값을 가지더라도 min(d[j], d[j-array[i]]+1)은 항상 d[j]의 값을 반환하기 때문이다. 다만 이해를 돕기 위해 코드에는 그대로 넣어주었다.

🤔 리뷰

• 관련 문제 풀어보기
• 문제 똑바로 잘 읽기
• DP 많이 풀어보면서 유형 익히기. 아무래도 익숙하지 않아서 노하우를 모르는 것 같기도...