문제
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.
예제 입력 1
3 10
1
2
5예제 출력 1
10문제 이해
각각 다른 가치를 지닌 n개의 동전을 적절히 조합하여 k원이 될 수 있는 모든 경우의 수를 구하는 문제(각각의 동전은 몇개라도 사용가능)
문제 분석
동전을 조합해 어떤 가치를 지니는 경우의 수를 찾는 문제는 동전의 가치가 다른 동전의 배수관계일 경우 그리디 문제로 풀 수 있다. 다만 이 문제의 경우 동전의 가치가 배수관계가 아니기 때문에 DP를 통해 직접 최적해를 구해야 한다.
자료구조
DP문제니 이 표를 직접 그리며 전체 경우의 수를 보며 규칙성을 찾으려고 했다. 전체 경우의 수를 보려고 하니 눈에 잘 보이지 않았다.
dp[T]배열을 통해 각각의 배열이 어떻게 변하는지 살펴보자.
우선 1원으로만 N원을 만드는 경우 N이 어떻게 변하던지에 상관없이 각각 한가지씩만 존재한다.
이제 1원에 2원을 더해 1원과 2원을 더했을 때 어떤 변화가 있는지 살펴보아야 한다.
1원에 2원을 더했을 때 나오는 동전의 경우의 수는 1원의 경우의 수를 그대로 가져간 채로 2원의 동전을 더했을 때 추가되는 경우만 고려하면됨
그러면 DP를 통해 이를 구현하고자 한다면 만약 1,2,5원을 통해 10원을 만드는 경우의 수를 구하고자 한다면 1,2원을 통해 10원을 만드는 경우의 수에 5원을 통해 만드는 경우의 수를 더하면 되지 않는가
또한 중요한 사실
초기값은 dp[0] = 1. 이는 0원을 만드는 경우는 동전을 사용하지 않는 한 가지 경우밖에 없기 때문.
이를 DP식 코드로 표현하자면 dp[T] += dp[T-현재 사용한 동전의 가치] 이라고 정의할 수 있다.
coin = 현재 사용 중인 동전의 가치
dp[j] += dp[j - coin]
j는 현재 계산 중인 금액
dp[j - coin]는 j - coin원을 만드는 경우의 수
이 경우의 수에 coin을 추가하여 j원을 만드는 경우의 수를 더해줌.
정답코드
#2293
import sys
N, T = map(int, sys.stdin.readline().split())
dp = [0] * (T+1)
dp[0] = 1
coins = []
for i in range(N):
coins.append(int(sys.stdin.readline()))
for coin in coins:
for j in range(coin, T+1):
dp[j] += dp[j-coin]
print(dp[T])
# 시간복잡도: O(NT)
