[Python] 백준(BOJ): 2293 동전1

문제

2293번: 동전 1

---

풀이

a.  접근법

N개의 동전을 사용하여 가치의 합이 K가 되는 경우의 수를 구해야 한다

knapsack 알고리즘을 이용하여 접근한다
ⓐ j가 coin[i]보다 작은 경우는, i번째 동전을 사용할 수 없으므로 DP[i][j] = DP[i-1][j]
ⓑ j가 coin[i]보다 크거나 같은 경우는, i번째 동전을 0개 ~ x(x*coin[i] <= j)개까지 사용할 수 있다.
      따라서 점화식은 DP[i][j] = DP[i-1][j-coin[i]] + DP[i-1][j] (coin[i] <= j)

 

b.  시간 초과 풀이

n, k = map(int, input().split())
coin = []
for i in range(n):
    coin.append(int(input()))
coin.sort()

dp = [0] * (k+1)
for j in range(coin[0], k+1):
    dp[0][j] = 1

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


print(dp[n-1][k])

계속해서 메모리, 시간 초과가 발생

런타임 에러의 경우, 동전의 가치에 대한 범위가 주어지지 않아서 발생함
(k의 범위는 1<k<10,000인데 동전의 가치는 100,000보다 작거나 같은 자연수 값을 가질 수 있음! 즉 k보다 큰 가치값을 가지는 동전 입력이 있을 수 있다는 말임) 

 

c.  풀이

i-1번째 DP에 i번째 DP를 덮어씌우는 방식으로 1차원 DP사용

n, k = map(int, input().split())
coin = []
for i in range(n):
    coin.append(int(input()))
coin.sort()

dp = [0] * (k+1)
dp[0] = 1

for val in coin:
    for i in range(val, k + 1):
        dp[i] += dp[i - val]

print(dp[k])