[BOJ, Python] 2293 - 동전 1 ( with Recursion, DP )

2293번: 동전 1

 

고등학교 확률과 통계 시간에 경우의 수 파트에서 다루는 내용이다. 주어진 동전의 종류에 따라, 합을 만들 수 있는 경우의 수를 구하는 문제이다. 처음에는 경우의 수 문제를 풀듯이 가장 가치가 큰 동전부터 하나씩 줄여가며 갯수를 세주는 방식으로 구현하였는데, 동전 종류의 개수가 고정이 아니므로 재귀를 활용하였다.

 

import sys
sys.setrecursionlimit(10**9)
n, k = map(int, input().split())
coins = list()
for _ in range(n):
    coins.append(int(input()))

# 동전의 가치를 내림차순으로 정렬
coins.sort(reverse=True)
ans = 0

# 재귀, coins 배열의 인덱스를 늘려가며 구현
def recur(idx, extra):
    global ans

	# 나머지가 0일 때 탈출
    if extra == 0:
        ans += 1
        return
	
    # 마지막 동전에 다다랐을 때, 나머지가 0이면 탈출
    if idx == len(coins) - 1:
        if extra % coins[idx] == 0:
            ans += 1
        return
	
    # 재귀
    for i in range(extra // coins[idx] + 1):
        recur(idx + 1, extra - i * coins[idx])

recur(0, k)
print(ans)​

 

해당 재귀를 구현하면서 피보나치 수열을 동적계획법과 재귀로 구현했을 때 효율에 문제가 되는 '반복되는 계산이 없다'는 생각에 시간 복잡도에 문제가 없다고 생각했는데, k의 값이 크고 동전의 가치가 낮고 많아질수록 상당한 시간이 걸렸다. 해당 문제는 기존에 접했던 DP 문제와는 사뭇 달랐는데, 이전 DP 배열에서의 계산이 계속해서 저장되는 것이 아니라 동전 별로 해당 동전이 사용되는 구간에서만 계산이 이뤄진다. 시간복잡도 계산은 익숙치 않아서 공부가 필요해보인다.

 

n, k = map(int, input().split())
coins = list()
for _ in range(n):
    coins.append(int(input()))

coins.sort()
ans = 0
dp = [0 for _ in range(k + 1)]
dp[0] = 1
# 낮은 동전 가치부터 탐색
for i in coins:
    for j in range(i, k + 1):
    	# ex) 합이 7이고 동전 가치가 5인 경우,
        # 합이 2인 경우의 수만큼을 더해준다.
        dp[j] += dp[j - i]

print(dp[-1])