BOJ(백준) 12865번 평범한 배낭 파이썬

12865번: 평범한 배낭

---

코드

import sys
r = sys.stdin.readline
N,K = map(int,r().split())
dp = [[0 for _ in range(K+1)] for _ in range(N+1)]
bag =[[0,0] for _ in range(N+1)]
for i in range(1,N+1):
    W,V = map(int,r().split())
    bag[i][0] = W
    bag[i][1] = V

for i in range(1,N+1):
    for j in range(1,K+1):
        w,v = bag[i][0],bag[i][1]
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], v + dp[i-1][j-w])

print(dp[N][K])

 

해설

사실 이번 문제는 해설이라고 말하기도 민망한 것이 밑의 결과를 보면 알겠지만 시간 복잡도가 거의 최악이다. 위 코드의 시간복잡도는 이중 포문때문에 O(N*K) 인데 그 중 K의 입력값이 1~100,000 사이이다 보니 발생한 참사라고 생각이 든다. 앞으로는 문제를 풀 때는 최악의 풀이를 고려한 후 너무 나이브하지 않게 풀이를 해야 겠다는 생각이 들었다.

그래도 코드에 대해 설명을 하자면 dp 를 0으로 채운 (N+1)*(K+1) 2차원 배열로 구성한 후 풀이를 시작하였다. dp 에서 row는 각각의 물건에 상응하고 column은 무게에 상응한다. 이 dp 를 활용하여 j 가 w 보다 작으면 이전 단계의 같은 무게인 dp[i-1][j] 을 입력해준다. 만약 j 가 w 보다 크거나 같으면 현재 물건을 입력할 수 있게 된다. 이 경우 현재 물건의 가치인 v 와 현재 위치의 무게 조건을 위배 하지 않는 선에서 추가할 수 있는 가치인 dp[i-1][j-w] 를 더한 값과 dp[i-1][j] 중 큰 값을 입력해준다. 포문을 모두 돌고 나면 위의 예제 1의 경우 다음과 같은 결과가 만들어진다.

 

결과