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])코드를 쓰기 전에 맞는 풀이라는 확신이 들 때까지 사고하자.
handsome