백준 12865 평범한 배낭 - 골드5 [파이썬]

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

12865번: 평범한 배낭

 

Knapsack 문제라고도 불리는 배낭문제다.

알고리즘을 처음 공부할 때 도대체 어떻게 푸는건지 3시간을 고민해도 못풀었던 문제인데

DP를 이용한 풀이를 공부한 뒤로 풀 수 있게 됐다.

 

예전에 비슷한 문제를 풀어본적이 있는데, 복습겸 한 번 더 풀어봤다.

지금 생각해도 DP는 경이롭다.. 

 

DP로 푼 코드(정답)

import sys
input = sys.stdin.readline

N, K = map(int, input().split(" "))
DP = [[0 for i in range(K+1)] for i in range(N+1)]
graph = [[0, 0] for i in range(N+1)]
for i in range(1, N+1):
    graph[i][0], graph[i][1] = map(int, input().split(" "))

# N은 100까지, K는 100,000까지, 총 10,000,000(1초) 필요
for n in range(1, N+1):
    for k in range(1, K+1):
        weight, value = graph[n][0], graph[n][1]
        # 탐색하려는 무게에 못미친경우 이전 무게를 그대로 가져옴
        if k < weight:
            DP[n][k] = DP[n-1][k]
        # 무게 범위 내일 경우
        else:
            # 현재 무게랑 현재 무게만큼 뺐을 때의 이전 값을 더한것과, 이전 값과 비교해서 큰거로 누적
            DP[n][k] = max(DP[n-1][k-weight]+value, DP[n-1][k])

print(DP[N][K])

 

백트랙킹으로 풀었다가 시간초과난 코드(오답)

# import sys
# input = sys.stdin.readline

# N, K = map(int, input().split(" "))
# graph = [[0, 0] for i in range(N)]
# for i in range(N):
#     graph[i][0], graph[i][1] = map(int, input().split(" "))

# answer = 0
# idx = 0


# def getMaxVal(idx, accw, accv):
#     if accw > K:
#         return

#     global answer
#     if idx == N:
#         answer = accv if answer < accv else answer
#         return

#     w, v = graph[idx][0], graph[idx][1]

#     getMaxVal(idx+1, accw+w, accv+v)
#     getMaxVal(idx+1, accw, accv)


# for i in range(N):
#     getMaxVal(i, 0, 0)  # idx, accweight, accval
# print(answer)

# 백트랙킹 했다가 시간초과 남.

결과