[알고리즘/백준] 2294번 동전2 Python 파이썬

 

이번 문제는 DP 문제로 이해하는데 좀 걸린 문제입니다. 아직 제대로 DP에 대해 알고 응용할 수 있는 정도까지는 아닌 것 같습니다. 다른 분의 풀이를 보면서 이해하는데 시간을 들었습니다.

 

 

동전의 종류와 특정 값이 주어지면 특정 값을 맞추기 위한 최소 동전 갯수를 구하는 문제입니다. 처음에 보았을 때 DP 문제인건 감을 잡았는데 어떻게 풀어나가야할지 값이 안 잡히더라고요 일단 DP 문제인 만큼 어떤 값을 누적시켜서 사용할 거고 dp 배열이 k+1 원만큼 만들어지면서 각 i원에 어떤 것을 저장시키지 않을까 생각했습니다. 그 이후에는 막혀서 결국 풀이를 찾게 되었습니다.

 

핵심은 "dp[i]에 dp[n-c1], dp[n-c2], dp[n-c3]  중에 가장 개수가 적은 경우를 택하고 +1" 한 값을 누적해주는 것입니다.

 

다음과 같은 코드로 통과하였습니다.

 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
n_list = [int(input()) for _ in range(n)]

dp = [0] * (k+1)

for i in range(1, k+1): # 1 # 2 .... # 5 ... # 12
    a = []
    for j in n_list: # 1 5 12 
        if j <= i and dp[i-j] != -1: # 1 # 1 .... # 1 5 ... # 1 5 12
            a.append(dp[i-j]) # 0 # 0 .... # dp[4] dp[0] # dp[11] dp[7] dp[0]
    if not a:
        dp[i] = -1
    else:
        dp[i] = min(a) + 1 # 1 # 2 .... # 1 ... # 4 4 1 -> 1
print(dp[k])

 

처음에 1 값이 들어오면 1원으로 만들 수 있기 때문에 dp[1-1] + 1 해줘서 결론적으로 dp[1] = 1

그 다음에 2 값이 들어오면 1원으로 만들 수 있어서 dp[2-1] + 1 해줘서 결론적으로 dp[2] = 2

마지막 12 값 경우 1, 5, 12 원으로 만들 수 있어서 dp[12-1] + 1(3+1) / dp[12-5] + 1(3+1) / dp[12-12] + 1(0+1) 값 중에서 최솟값이니 결론 값이 dp[12] = 1 이 되게 됩니다. 

 

아직까지는 코드보면서 이해하고 따라가는 수준이고 아직 응용할 수 있거나 스스로 풀기에는 힘든 것 같습니다. 앞으로 DP 문제를 많이 접해보면서 공부해야할 것 같습니다.