문제
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
난이도
Gold 5
입력 조건
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
출력 조건
첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.
입력 예시
3 10
1
2
5
출력 예시
10정답 코드
import sys
n,k = map(int, input().split())
coins = [int(sys.stdin.readline()) for _ in range(n)]
d = [0] * (k+1) # 가치의 합이 index가 되는 경우의 수를 담고 있는 DP 테이블. 0으로 세팅
d[0] = 1
for i in coins:
for j in range(i,k+1):
if j-i>=0:
d[j] += d[j-i]
print(d[k])느낀 점
이 문제 역시 다이나믹 프로그래밍 문제이다.
원래 풀던 방식대로 대충 흐름 잡고 점화식 놓으려니까 절대 안풀렸다..
문제에서 주어진 동전의 가치에 따라 DP테이블을 갱신하는 방식으로 풀었어야 했다.
예컨데 예제에서 동전이 각각 1,2,5원 짜리가 주어졌으므로 1원부터 만들수 있는 경우를 갱신한다.
그렇게 되면 각각의 동전마다 d[j] = d[j] + d[j-i]라는 점화식을 구할 수 있다.
굉장히 시간도 오래걸리고 애를 먹은 문제다.
결국 못풀어서 풀이를 보고도 한참을 이해하는데 시간이 걸렸다. 앞으로 이런 유형의 문제도 마주쳤을 때 당황하지 않도록 꼭 기억해놓자
