백준 2293 [python]

https://www.acmicpc.net/problem/2293

DP를 풀 때 최적화된 풀이를 위한 점화식을 세우는데 더 공들여야겠다. 이상한 풀이로 시간 초과와 메모리 초과를 많이 당했다. 처음에 대충 생각해놓고 코드를 짜니 답이 없다. 더 집중해서 생각한 다음 코드를 적자.

ㅂㅅ코드1 (시간 초과)
이 코드는 동전을 돌며 세고 빼는 것을 반복해서 결국 0에 몇번 도달했냐를 계산한 후 0을 출력. 0은 k가 나눠지고 빼져서 k -> 0이 되었기 때문에 k가 한 번 만들어졌음을 의미. 엉망이다.

import sys

n, k = map(int, input().split())
coins = []
for i in range(n):
    coins.append(int(sys.stdin.readline()))
coins.sort(reverse=True)

res = [0 for i in range(10001)]
res[k] = 1

for coin in coins:
    temp_list = [i for i in range(10001) if res[i] != 0]
    for val in temp_list:
        for i in range(1, val // coin + 1):
            res[val - coin * i] += 1
print(res[0])

ㅂㅅ코드2 (시간 초과)
dp를 이차원 리스트로 하고 재귀함수로 dp값을 찾는 구조. find_dp 안의 점화식을 수정하면 시간 초과는 해결될 듯.

import sys

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

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

def find_dp(idx, val):
    if dp[idx][val] != -1: return dp[idx][val]
    sum = 0
    for i in range(val // coins[idx] + 1):
        sum += find_dp(idx - 1, val - i * coins[idx])
    dp[idx][val] = sum
    return sum

print(find_dp(n - 1, k))

ㅂㅅ코드3 (시간 초과)
위의 코드가 재귀함수를 사용했다면 이 코드는 for문으로 dp를 채우는 구조. 이것도 점화식이 잘못되어 시간 초과가 났다.

import sys

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

dp = [[1 if i == 0 or (j == 0 and i % coins[0] == 0) else 0 for i in range(k + 1)] \
for j in range(n)]

for i in range(1, n):
    for j in range(coins[i]):
        dp[i][j] = dp[i - 1][j]
    for j in range(coins[i], k + 1):
        m = j
        while True:
            dp[i][j] += dp[i - 1][m]
            m -= coins[i]
            if m < 0: break 

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

코드4 (메모리 초과)
엉망인 점화식을 고쳐서 이중for문에서 마무리되게 했다. 메모리 초과가 해결되기 위해서는 일차원 리스트 dp에 같은 방식으로 값을 덮어씌우면 된다.

import sys

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

dp = [[1 if i == 0 or (j == 0 and i % coins[0] == 0) else 0 for i in range(k + 1)] \
for j in range(n)]

for i in range(1, n):
    for j in range(coins[i]):
        dp[i][j] = dp[i - 1][j]
    for j in range(coins[i], k + 1):
            dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]
            
print(dp[n - 1][k])

제출한 코드.

import sys

n, k = map(int, input().split())
coins = []
dp = [1 if i == 0 or i % coins[0] == 0 else 0 for i in range(k + 1)]
for i in range(n):
    coins.append(int(sys.stdin.readline()))
coins.sort()

for i in range(1, n):
    for j in range(coins[i], k + 1):
            dp[j] += dp[j - coins[i]]
            
print(dp[k])

코드를 쓰기 전에 맞는 풀이라는 확신이 들 때까지 사고하자.