[백준, 파이썬] 2293번 동전 1

다이나믹 프로그래밍을 이용하여 해결하는 문제중 하나인 동전 1 문제입니다. 

dp문제가 그렇듯이 점화식을 못찾으면 몇시간이 걸리기기도, 찾기만 하면 10분만에도 푸는 그런 문제입니다..

난해하지만 점화식을 그림으로 표현해 보았습니다. 

입력받은 동전의 종류를 오름차순으로 정렬하여 순차적으로 접근합니다. 

먼저 db라는 리스트를 구하려 하는 가치 k에다 +1 더한 사이즈 만큼 초기화를 합니다. 

여기서 가장 중요한 것은 반드시 dp[0]요소를 1로 초기화 한다는 점인데요, 

가치가 0을 만드는 조합의 경우의 수가 아무것도 선택하지 않는 1가지 경우가 있기 때문입니다.

 

dp 리스트는 위 예시에서

1. coin 1 만 이용하는 경우,

2. coin 1,2 이용하는 경우

3. 주어진 코인 1,2,3 모두 이용하는 경우 

이와 같이 주어진 동전의 갯수 번 만큼 업데이트 됩니다. 

 

위 예시에서 1원을 이용할 경우 모든 가치에 대해서 1원으로 만드는 경우가 하나씩 존재하므로 

dp는 위와같이 모두 1로 초기화 됩니다. 

 

두번째 코인에 대해서 dp 를 업데이트 하는 과정에서 규칙을 찾을 수 있었는데요, 

"어떠한 가치에 k에 대해서 1,2원을 가지고 만드는 경우의 수는 몇 가지일까" 를 고민하던 중 

이전까지 구한 dp[k-2]에 기존의 dp[k]를 더하면 새로운 dp[k]를 구하는

dp[i] = sigma(dp[i] + dp[i-coin[j]]) 점화식을 찾게 되었습니다.

이 부분을 위 그림의 초록색 화살표로 표시하였는데요,

 

따라서 이를 기반으로 코드를 짜면 다음과 같습니다. 

 

n, k = map(int, input().split(' ')) coin = [] dp = [] def init(k): for i in range(n): coin.append(int(input())) coin.sort() for k in range(k+1): dp.append(0) dp[0] = 1 def solve(k): init(k) for j in coin: for i in range(k+1): if not j > i: dp[i] = dp[i] + dp[i-j] print(dp[k]) solve(k)