[2293] 동전 합 1

😲 문제

출처
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

❗️ 문제 재정의

n가지 동전으로 중복허용하여 k원이 되도록하는 경우를 말하여라.

중복 배낭 문제(Knapsack Problem with Repetitions)와 유사한 문제이다.
동전의 수는 정해져 있다. 해당 동전을 어떻게 조합할 것인가를 묻는 문제이다.
동전을 한 종류씩 순차적으로 사용하면 된다.

주의할 점은 동전의 중복사용은 가능하지만 동전의 조합이 중복되지 않고 순서가 중요하지 않다는 점이다.

점화식을 세워보면
d[i] = d[i] + d[i-coin]이 되겠다.
금액 i를 만드는 방법의 수는,
금액 i에서 현재 동전의 가치 coin을 뺀 금액을 만드는 방법의 수에
현재 동전을 추가하는 방법의 수와 같다는 것을 의미

✔ 계획 수립

1. n,k를 입력받고 각각의 동전의 가치를 입력 받는다.
2. 모든 동전을 하나씩 순차접근한다.
3. 해당 동전을 사용하여 가치 i를 만드는 경우의 수를 구하면 된다.
   d[i] = d[i] + d[i-coin]
4. 마지막 가치 k의 개수를 출력

👨🏻‍💻 문제 풀이

# 동전의 종류, 만들어야 하는 가치
n , k = map(int, input().split())
d = [0] * (k+1)
coins = []
for i in range(n):
    coins.append(int(input()))
d[0] = 1 # 0을 만드는 경우는 1가지
for coin in coins:
    for i in range(coin, k+1):
        d[i] += d[i-coin] # d[i] = d[i] + d[i-coin]
print(d[k])

😅 회고

점화식만 잘 세우면 문제가 없다!
점화식을 생각하기에 약간 시간이 걸렸지만 대표적인 dp문제이기에 바로 생각이 났다.
점화식을 세울줄 아냐를 물어보는 문제같다.