[Python] 백준 2293번 : 동전 1

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

2293번: 동전 1

---

💡 문제 풀이

DP 문제이다! 역시 점화식만 고민하면 되는 문제이다.

 

주어진 코인을 기준으로 연산을 실행하고 이전 경우를 따지면서 계산해주면 된다.

문제를 예로 들면, 1을 기준으로 시작한다.

2는 1을 만드는 방법에서 1만 추가해준 것이다. 또, 3은 2를 만드는 방법에서 1만 추가해준 것이다.

즉, 1원이 기준일 때는 경우의 수가 변화가 없다. 1만 추가하면 되기 때문이다.

2를 기준으로 잡았을 때,

2를 만드는 방법에 2가 새롭게 추가된다. 즉 기존 값에서 1가지 경우가 추가된다.

3은 1+2로 2원을 만드는 방법에서 1만 추가해준 것이다. 그래서 DP[1]인 1이 추가된다.

마지막으로 4는 3+1과 2+2와 같다. 즉 2를 만드는 방법에서 2를 추가한 것과 3을 만드는 방법에서 1을 추가한 것과 같다.

 

이런 식으로 특정 동전을 기준으로 계산해주면 된다.

✔️ 느낀 점

DP 문제는 정말 점화식 찾기, 초기값 찾기 문제이다. 이 문제도 그걸 찾기가 너무 힘들어서 한참 고민했다..

정말 DP는 나랑 안 맞는 것 같다..

💻 코드

import sys

n, k = map(int, sys.stdin.readline().split())
coins = [int(sys.stdin.readline()) for _ in range(n)]
DP = [0 for _ in range(k+1)]
DP[0] = 1
for i in coins:
    for j in range(1, k+1):
        if j-i >= 0:
            DP[j] += DP[j-i]
            
print(DP[k])