백준 2293 동전 1

유형 : dp

 

첫번째 오답

 동전들의 가치가 1, 2, 5로 주어지는 경우를 예로들면, 단순히 가치 i를 만드는 경우의 수 dp[i] = dp[i-1]+dp[i-2]+dp[i-5] 로 만드는 경우에는, 중복된 경우를 따로 카운트하게 되어 오답이 된다. 예를들면 i=3 인 경우를 예로 들면, dp[2]+dp[1]이 되는데, dp[2]를 사용하는 경우를 살펴보면, dp[2]는 1을 두개 쓴 경우와 2를 한개 쓴 경우 해서 2가지가 되고, 여기에 1을 한개 더 사용하여 3을 만드는 경우이므로 총 2가지 (1을 3개), (1을 1개, 2를 1개)가 된다. dp[1]은 1을 한개 사용하는 경우 한가지가 존재하고, 여기에 2를 한 개 사용하여 3을 만드는 경우가 되므로, (1을 1개, 2를 1개) 한가지가 된다. 따라서 dp[3] = 3 이라고 계산하게 되는데, 위의 세가지를 살펴보면 (1을 1개, 2를 1개) 가 두번 세어진 것을 알 수 있다. 즉, 1을 먼저 쓰고 2를 쓴 경우와, 2를 먼저 쓰고 1을 쓴 경우를 다르게 체크하는 것이다.

 따라서 이러한 중복되는 경우의 수를 피하기 위해 아래에서는 n 종류의 동전만을 사용하는 경우를 나누어서 계산하게 된다.

 

풀이 및 두번째 오답

 먼저 dp를 n x k+1 사이즈의 리스트로 선언한다. dp[n][k]는 첫 n+1개의 코인(0부터 세니까)을 사용하여 가치 k를 만드는 경우의 수이다. dp[0]의 경우에는 첫번째 동전만을 사용하는 경우이므로, dp[0]의 경우,

[1]+[1 if i%coin[0]==0 else 0 for i in range(1,k+1)] 로 초기화 해준다. 즉, k가 coin[0]으로 나누어지는 경우에만 가치 k를 첫번째 코인만으로 만들수 있다. 그 후의 점화식은 아래와 같다.

$dp[i][j]=\begin{cases}dp[i-1][j], & \mbox{if j < coin[i]} \\ dp[i][j-coin[i]]+dp[i-1][j], & otherwise\end{cases}$

 첫 경우는, 만드려는 가치 j가 i번째 코인의 가치보다 작은 경우로, 이러한 경우에는 i번째 코인을 사용할 수 없으므로, 전의 것을 그냥 사용하면 된다. 두번째 경우에서 dp[i][j-coin[i]]는 i번째 코인도 사용해서 가치 j-coin[i]를 만든 후에 i번째 코인을 사용하는 경우이고, dp[i-1][j]의 경우에는 i번째 코인을 사용하지 않는 경우가 된다. 이렇게 계산하면 위의 오답의 예를 다시 살펴보면 dp[1][3] (첫번째, 두번째 코인을 사용하여 가치 3을 만드는 경우의 수)는 dp[1][1] + dp[0][3] 이 된다. dp[1][1]의 경우에는 dp[0][1]로 주어지므로, 1이 되고, dp[0][3] 역시 1이므로, 위와 같이 중복된 경우는 세지 않을 수 있다. 

Python Code

import sys
n, k = map(int,sys.stdin.readline().split())
 
coin=[]
for _ in range(n):
    c = int(sys.stdin.readline())
    if c <=k:coin.append(c)
n=len(coin)
 
dp = [[1]+[1 if i%coin[0]==0 else 0 for i in range(1,k+1)]]+[[1]+[0 for i in range(1,k+1)] for j in range(1,n)]
for i in range(1,n):
    for j in range(coin[i]):
        dp[i][j] = dp[i-1][j]
    for j in range(coin[i],k+1):
        dp[i][j] += dp[i][j-coin[i]]+dp[i-1][j]
print(dp[n-1][k])

코드로 나타내면 다음과 같은데, 문제는 dp의 공간 복잡도가 $O(n\dots k)$가 되어 메모리 초과가 된다.

 

공간복잡도 줄이기

 그런데, 위의 코드를 살펴보면 실질적으로 dp[i][j]를 계산하는 13, 15 line에서 dp[i-1][j]가 계속 반복되는 것을 볼 수 있다. 즉, dp를 길이 k+1인 리스트로 선언한 후 15번째 줄의 우항의 마지막 항을 버리면 된다.

 

Python Code

dp = [1]+[1 if i%coin[0]==0 else 0 for i in range(1,k+1)]
 
for i in range(1,n):
    for j in range(coin[i],k+1):
       dp[j] += dp[j-coin[i]]
 
print(dp[-1])

 

문제링크