[BOJ][Python]12865번 풀이

길었던 대장정의 끝입니다. 정말 오랫동안 고민했던 문제입니다만 결국 온전히 제 힘만으로는 풀어내지 못했네요. 배낭 문제는 많으니까 다음에 다른 문제를 혼자서 풀어서 설욕을 해야겠어요.

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

12865번: 평범한 배낭

import sys
ssr = sys.stdin.readline

n,k = map(int, ssr().split())
t = [[0 for _ in range(k+1)] for _ in range(n+1)]
items=[[0,0]]
for _ in range(n):
    items.append(list(map(int, input().split())))
for i in range(n+1):
    for j in range(k+1):
        w = items[i][0]
        v = items[i][1]
        if j < w:
            t[i][j] = t[i-1][j]
        else:
            t[i][j] = max(v + t[i-1][j-w], t[i-1][j])
print(t[n][k])

일단 해당 문제를 편하게 풀기 위해서는 가방에 넣을 물건의 리스트를 미리 만드는 쪽이 유리합니다. 이미 table에 채우기 시작하면 자꾸 뭔가 어긋나는 것 같아요. 최대 n*k번의 반복이 필요하니까 대략 10,000,000 정도의 반복문의 실행이 일어나고 시간제한에 걸리게 되더라구요. 그래서 인덱스로 물건에 접근할 수 있도록 만들어놓고 풀어야 합니다.

 

나머지는 별 거 없어요. 조건에 따라 이전 행의 값을 그대로 쓰거나 새로운 값으로 교체하거나 하는 겁니다. 그걸 위해서 max()를 이용하구요.

 

오롯이 혼자 힘으로 풀어내지 못했다는게 마음에 걸리긴 합니다만... 내일 부터는 배낭 문제 정복하기를 해야겠습니다.