평범한 배낭 (12865 번)

12865번: 평범한 배낭

 

나의 풀이

import sys

def _main(k, items):
    answer = [0] * k
    for w, v in items:
        for j in range(k-1, w-2, -1):
            if (j == (w - 1)):
                answer[j] = max(answer[j], v)
            else:
                answer[j] = max(answer[j], answer[j - w] + v)
    return max(answer)

n, k = map(int, sys.stdin.readline().rstrip().split())
items = [tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
print(_main(k, items))

 

시간 복잡도

for w, v in items : 배낭 갯수 만큼 순회 ( 선형 시간 복잡도 )
    for j in range(k-1, w-2, -1) : 가능한 무게만큼 순회 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )