[백준] 2293번: 동전 1

문제

백준 - 2293번: 동전 1

분석

n가지의 동전의 종류로 합이 k가 되는 경우의 수를 구하는 문제이다.
동전은 여러번 사용해도 사용 가능하다. 그러나 구성이 같고 순서만 다른 경우는 하나의 경우로 간주한다.

마지막 문장인 "순서만 다른 경우는 하나로 간주" 때문에 이 문제가 dp에서 필수 문제가 된거 같다.
보통 1, 2, 3 더하기 문제같은 경우 순서만 다른 경우도 다른 가짓수로 쳤기 때문에
이중 for문에서 바깥 for문이 합, 안쪽 for문이 종류(1, 2, 3)을 의미하여 그 전 상황을 이어 받기만 해도 됐다. 그러나 순서가 다른 중복되는 경우를 제외해야 했기 때문에 이 문제는 for문의 순서를 바꿨다.

각 코인을 추가 고려할 때마다 dp 배열을 쭉 돌려주면 중복을 피할 수 있다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = []
for _ in range(n):
    coins.append(int(input()))
dp = [0]*(k+1)
dp[0] = 1
for coin in coins:
    for i in range(1, k+1):
        if i >= coin:
            dp[i] += dp[i-coin]
print(dp[k])

끝으로..

dp에서 순서만 다른 중복을 피하는 방법에 대해 배울 수 있어서 좋았다.