[Python] 백준 12865번 - 평범한 배낭

문제

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

 

---

표준 입력을 위해 sys모듈 추가.

표준 입력으로 대체.

물품의 수(N)과 버틸 수 있는 무게(K)를 입력받음.

K+1개의 0을 갖는 리스트 N+1행을 생성(2차원 리스트).

=> [N+1]행 [K+1]열

물건 정보를 저장하기 위한 리스트 생성.

=> [0, 0]을 N+1개 갖는 2차원 리스트 생성.

=> 0번째 인덱스는 무게, 1번째 인덱스는 가치를 의미함.

물건 정보를 입력받아 리스트에 저장.

import sys


input = sys.stdin.readline
N, K = map(int, input().split())
dp = [[0] * (K+1) for _ in range(N + 1)]
item = [[0, 0] for _ in range(N + 1)]

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

 

물건을 하나씩 가져오기 위해 반복(1부터 N까지).

- 가방의 무게를 1씩 증가시켜 가져오기 위해 반복(1부터 K까지)

-- 만약 해당 물건이 가방 무게 이하라면.

--- 현재 물건의 가치 + 현재 물건의 무게를 뺀 경우에 대한 가치가 이전 물건의 대한 가치보다 큰 경우 갱신.

--- 아니면 이전 물건의 가치를 그대로 저장.

-- 아니면 이전 물건의 가치를 그대로 저장.

리스트의 맨 마지막([N][K])를 출력.

# [무게, 가치]
for i in range(1, N + 1):  # 물건의 번호
    for w in range(1, K + 1):  # 가방의 무게
        if item[i][0] <= w:  # 현재 물건의 무게가 가방 무게 이하라면
            if item[i][1] + dp[i-1][w-item[i][0]] > dp[i-1][w]:
                dp[i][w] = item[i][1] + dp[i-1][w-item[i][0]]
            else:
                dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = dp[i-1][w]
print(dp[N][K])

 

전체 코드.

import sys


input = sys.stdin.readline
N, K = map(int, input().split())
dp = [[0] * (K+1) for _ in range(N + 1)]
item = [[0, 0] for _ in range(N + 1)]

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

# [무게, 가치]
for i in range(1, N + 1):  # 물건의 번호
    for w in range(1, K + 1):  # 가방의 무게
        if item[i][0] <= w:  # 현재 물건의 무게가 가방 무게 이하라면
            if item[i][1] + dp[i-1][w-item[i][0]] > dp[i-1][w]:
                dp[i][w] = item[i][1] + dp[i-1][w-item[i][0]]
            else:
                dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = dp[i-1][w]
print(dp[N][K])