이코테 8-8 효율적인 화폐구성 파이썬

이코테 8-8 효율적인 화폐구성 파이썬 풀이

접근방식

1. 화폐종류를 입력받습니다.
2. 초기 값이 10001인 dp 리스트를 만듭니다.
3. 이중 for문을 활용하여 각각의 화폐 단위별로 가장 작은 최솟값을 구하도록 해줍니다.

import sys
input = lambda:sys.stdin.readline().rstrip()

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

# 화폐 종류 리스트
type=[]

for _ in range(n):
    type.append(int(input()))

dp = [10001] * (m+1)

dp[0] = 0

for i in range(n):
    for j in range(type[i], m+1):
        if dp[j-type[i]]  !=10001:
            dp[j] = min(dp[j], dp[j-type[i]] + 1)

# 10001이라는 것은 가지고 있는 화폐구성으로 만들 수 없음을 의미
if dp[m] == 10001:
    print(-1)
else:
    print(dp[m])

# print("dp", dp)
# dp [0, 10001, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5]

작동 원리 분석

for i in range(n):
    for j in range(type[i], m+1):
        if dp[j-type[i]]  !=10001:
            dp[j] = min(dp[j], dp[j-type[i]] + 1)

2와 3 화폐를 가지고 15를 만든다는 가정을 해보겠습니다.

i == 0인 경우, type[0] = 2입니다.

• j in range(2, 16) for문이 돌아가게 되고,
  • j가 2인 경우,
    • dp[2-2] != 10001:
      • dp[2] = min(dp[2], dp[0] + 1) = 1이 됩니다.

맨 처음, dp[0] = 0으로 설정해줬기 때문에 자기자신을 포함한 구성을 시작할 수 있습니다.
이를 반복하면,

• j가 4인 경우,
  • dp[4-2] != 10001:
    • dp[4] = min(dp[4], dp[2] + 1) = 2가 됩니다.

결국, i == 0인 경우, dp[2] = 1, dp[4] = 2, … ,dp[16] = 8로,
2의 배수자리에 모두 2로 나눈 몫이 들어가게 됩니다.

마지막으로, i==1인 경우 type[1] = 3이기 때문에,
해당하는 위치의 수가 3을 포함한 조합으로 만들 수 있다면, 그 값이 최솟값을 가지게 되고,
자연스럽게 갱신이 되어, 이 예시의 경우 최종적으로 dp 리스트는
dp [0, 10001, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5] 의 모습으로 바뀝니다.

이 문제는 다이나믹 프로그래밍 문제로, 조합을 구하기 위해 단순히 나눗셈을 이용하는 것이 아니라,

메모이제이션 기법을 활용한 dp 리스트로 해결하는 문제입니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady