백준 알고리즘 2294. 동전 2

https://www.acmicpc.net/problem/2294

2294번: 동전 2

 

전체 코드

import sys

n, k = map(int, input().split())
coins = set()

for _ in range(n):
    coins.add(int(sys.stdin.readline().strip('\n')))

# 가치의 최대합은 10000이다. 0~10000까지의 값을 col로 사용하기 위해 10001로 초기화한다.
max_size = 10001
# 각 리스트의 최대 값은 10001을 넘지 않는다. 최대값을 inf로 지칭한다.
inf = max_size
dp = [0] * max_size
for i in range(1, max_size):
    # [0, inf, inf, inf...]으로 초기화된다.
    dp[i] = inf

for coin in coins:
    # coin~k 까지 순회하면서 동전 개수를 업데이트 한다.
    for j in range(coin, k + 1):
        # 동전의 j = coin일 때 coin 1개로 j를 계산할 수 있다는 의미이다.
        # dp[0]은 항상 0이므로 dp[j]는 항상 '1'이다.
        dp[j] = min(dp[j], dp[j - coin] + 1)

print(-1 if dp[k] == inf else dp[k])

 

풀이

1<=k<=10000이므로 dp 테이블을 위한 리스트를 10001 크기로 생성한다. 이 후 0을 제외한 모든 값을 inf(=10001)로 초기화한다.

각 코인 리스트를 coin 변수로 순회하며 리스트 j를 "coin~k" 범위로 순회한다.

 

dp[0]은 0으로 초기화되어 있기 때문에 dp[0]+1 은 항상 1이다. j-coin= 0일 때 min(dp[j], dp[j-coin]+1)은 항상 1을 반환한다.

이는 값 3이 동전 3 1개로 표현 가능하다는 뜻이다.

 

 

dp[j-coin]이 inf면 dp[j]도 inf가 된다. 이는 동전 3만으로는 값 4, 5 등의 값을 구할 수 없다는 의미이다.

 

이렇게 루프를 순회하고 나면 다음과 같이 각 인덱스에 해당하는 값에 동전 3의 개수가 초기화된다.

 

이제 동전 6으로 순회해본다. 

 

min(dp[0]+1, dp[6])=1 이기 때문에 dp[6]=1로 저장한다. 값 6은 동전 3으로는 2개로 표현가능하나, 동전 6 1개로 표현 가능하기에 최소값을 반영한다.

 

j=9에서는 다음과 같이 min[dp[3]+1, dp[9]) = 2가 되어 해당 값을 반영한다. 값 9를 동전 6, 동전 3 각각 1개로 표현한다고 볼 수 있다.

 

이를 반복하면 다음과 같이 초기화 된다.

 

마지막으로 11 역시 동일하게 진행된다.

 

 

 

마지막 k의 값이 최소 동전 개수가 되므로 dp[k]를 반환한다. 그러나 만약 동전이 [4, 9]일 경우 15가 다음과 같이 inf가 될 수 있다. dp[k]==inf면 -1을 반환한다.