문제:

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

입력:

첫째 줄에 n, k가 주어진다. (1<=n<=100, 1<=k<=10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100.000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

풀이 방법:

대표적인 동적계획법으로 풀어야 하는 문제이다. 점화식은 다음과 같이 나타낼 수 있다. 
 
dp[i]=dp[i-coins]

즉 예시로 보면 dp[i]=dp[i-1]+dp[i-2]+dp[i-5] 인 것이다.
하지만, 동전의 갯수는 최대 100개까지 주어질 수 있으므로 너무 많은 호출이 발생한다. (stackoverflow)
따라서 이를 해결하기 위해서 메모리제이션 방법을 사용하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
n,k=map(int,input().split())
coins=[]
for i in range(n):
    coins.append(int(input()))
 
dp=[0]*(k+1)
dp[0]=1
 
for coin in coins:
    for i in range(coin,k+1):
        dp[i]+=dp[i-coin]
print(dp[k])
cs


'Algorithm > Python' 카테고리의 다른 글

[BOJ]1476. 날짜 계산  (0) 2019.06.27
[BOJ]1002.터렛  (0) 2019.05.21
[BOJ]7568. 덩치  (0) 2019.05.19
[BOJ]2231. 분해합  (0) 2019.05.18
[BOJ]2309. 일곱 난쟁이  (0) 2019.05.17

+ Recent posts