[백준] 평범한 배낭

박형진·2022년 1월 27일
0

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


1. 전체 코드

import sys

# 물품의 수, 최대 무게
n, capacity = map(int, sys.stdin.readline().rstrip().split())
cargo = []
for _ in range(n):
    w, v = map(int, sys.stdin.readline().rstrip().split())
    # (가치, 무게) = (v, w)
    cargo.append([v, w])
pack = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for c in range(1, capacity + 1):
        # i번째 물건의 무게가 배낭의 용량보다 작다면 (=일단 넣을 수 있기라도 한다면)
        if cargo[i-1][1] <= c:
            a = cargo[i-1][0] + pack[i-1][c - cargo[i-1][1]]
            b = pack[i-1][c]
            pack[i][c] = max(a, b)
        else:
            pack[i][c] = pack[i-1][c]
print(pack[-1][-1])

2. 후기

처음부터 완전한 크기의 pack배열을 선언하지 않고, for문마다 한 행씩 생성했을 경우 시간초과가 발생했다. 상향식 풀이인 타뷸레이션 방식을 사용했다.

profile
안녕하세요!

0개의 댓글