DP 응용문제(이코테) - 2

날짜 : 2022. . 

사용 언어 : python

 

문제

 

코드

import sys

n, m = map(int, sys.stdin.readline().split()) # 화폐의 종류 개수, 총 금액
coin = []
dp = [10001] * (m + 1) # 10001 : 임의의 값(무한대)
dp[0] = 0

for i in range(n): coin.append(int(sys.stdin.readline())) # 화폐가치 입력
for i in coin: dp[i] = 1 # 코인 하나로 만들 수 있는 수

for i in range(n): # 화폐 종류 개수별로 for문
    for j in range(coin[i], m + 1): # 해당 코인 기준으로 for문 돌림
        if dp[j - coin[i]] != 10001: dp[j] = min(dp[j], dp[j - coin[i]] + 1) # (i - k)원을 만드는 방법이 존재하는 경우

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

 

 

풀이

- 화폐 종류의 개수와 달성해야 할 총 금액을 입력받는다.

- 이후 금액에 따른 사용된 화폐 개수를 저장할 리스트(dp)를 생성한 후 무한대로 대표되는 임의의 값(10001)을 설정한다.

- 0의 경우 아무화폐도 사용하지 않았기 때문에 0으로 설정

- 화폐가치와 1개로 만들 수 있는 경우를 입력

- 저장된 화폐의 종류별로 for문을 돌린다.

- 해당 for문 내부에 i값(해당되는 화폐)을 기준으로 for문을 돌리고 해당되는 값을 만드는데 사용된 코인 개수를 최소값으로 최신화한다.(만들 수 있는 값이 있는 경우)

ex) 2 : 2로 만들 수 있는 값에 대해서 오름차순으로 전개해 나가면서 저장 -> 2, 4, 6, 8, 10 ... 

-> 4 : 4로 만들 수 있는 값에 대해서 전개하면서 저장 -> 4, 8, 10, 12, .... => 4의 배수의 경우 최솟값으로 갱신

- 이후에 해당되는 값이 존재하는 경우 그 값을 출력하되 없는 경우에는 -1을 출력한다.

 

 

알게된 점

- 이중 for문에서 for j in range(coin[i], m + 1) 을 연상해내지 못했다.

- 조금 방식이 복잡해지니까 바로바로 떠올리지 못한 것 같다.

 

 

참고 사이트

-