[백준] 2293 - 동전1 (Python)

문제 출처:

www.acmicpc.net/problem/2293

2293번: 동전 1

문제 풀이:

• DP 문제는 보통 점화식을 찾으면 끝나기 때문에 점화식을 찾으려 했는데 아무리 봐도 점화식이 안 보여서 애먹은 문제이다.
• 이 문제는 코인별로 점화식을 따로 봤어야 하는 문제인데 난 한 번에 같이 보려다 보니 어려웠다.
• 직접 예제를 적어가면서 보면 더 쉽게 보인다. k=10이고 동전은 1,2,5인 경우를 보자

k	1	2	3	4	5	6	7	8	...
1원	1	1	1	1	1	1	1	1	...
2원	0	1	1	2	...	...	...	...	...
5원	0	0	0	0	...	...	...	...	...
총합(dp)	1	2	2	3	...	...	...	...	...

• k가 4인 경우를 보면 2원으로 만들 수 있는 경우는 2원 짜리 동전을 1개 쓴다고 생각하면 4원에서 2원짜리 동전 한개를 쓰고 dp[2]가 남는다. 즉 2원짜리를 1개 쓴다고 생각하면 4원에서 2원을 빼고 2원을 만들 수 있는 경우의 수 이기때문이다. 이처럼 각각의 동전의 경우를 갱신해주면 된다. 
• 여기서 한가지 더 나가야하는데 dp값은 최종적으로 다 더해줘야한다는 것이다. 즉 최종적인 dp[4]를 구할땐 1원 짜리 썻을때 dp[4]와 2원짜리 썻을때 dp[4]를 각각 더해주어야 최종적인 dp[4]를 구할 수 있다.

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

for _ in range(n):
    coins.append(int(input()))

dp=[0]*(k+1)
dp[0]=1

for i in coins:
    for j in range(i,k+1):
        print(j,end='\t')
        dp[j] += dp[j-i]

print(dp[k])