[백준2294번] 동전2(파이썬)

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

2294번: 동전 2

이 문제같은 경우에는

나동빈님이 쓰신

이것이 코딩테스트다에 수록된

DP 대표유형에 속한 문제입니다.

처음에 문제의 풀이를 쭉 따라가도

이게 뭔소리지 하다가

직접 코드를 몇 번 쳐보고서야

이게 이런 의미이구나를 깨달았습니다.

 

이 문제를 DP로 풀기위해

이렇게 테이블을 쭉 그려봤습니다.

예시의 케이스를 가져와봤습니다.

동전 1이 있으므로

1부터 4까지 하나씩 증가하다가

5부터는 다시 1이 됩니다.

그 이유는 동전 5가 있기 때문이죠.

그렇게 계속 증가하다가

10에서 2가 됩니다.

5 2개를 쓸 수 있기 때문이죠.

그렇게 보면

현재 i번째 dp는

(i-동전의 수+1) 중

가장 최솟값에 해당합니다.

그러니 15에서는

12 1 1 1-->4 대신

5 5 5 -->3이 되는 것이죠.

코드를 보면 이렇게 됩니다.

 

 

#백준 2294 동전2
from sys import stdin

n,k=map(int,stdin.readline().split())

coin=[]
for _ in range(n):
  c=int(stdin.readline().rstrip())
  coin.append(c)



dp=[10001]*(k+1)
dp[0]=0
for num in coin:
  for j in range(num,k+1):
    dp[j]=min(dp[j],dp[j-num]+1)

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

 

DP문제는 

프로그래밍 피지컬보다는

'뇌지컬'이 요구되는 문항이라

체감난이도가 높게 느껴집니다.

그냥 이런 류의 문제를

많이 풀고

코드를 많이 보고

직접 손으로 치면서

손으로 익히는 것 밖에는

왕도가 없어보이네요.