[파이썬, 자바] 백준 12865 : 평범한 배낭 (골드5)

[파이썬, 자바] 백준 12865 : 평범한 배낭 (골드5)

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

---

풀이

방향성 생각

• 냅색 기본문제
• state는 n번째 가방 / 무게 k이다.
• 현재 노드가 n,k이면 물건을 가방에 담기 전 무게는 k-w이다.
• 또한, 가방에 물건을 담지 못하는 경우도 계속해서 업데이트 해준다.

 

---

파이썬

import sys
input = lambda : sys.stdin.readline().rstrip()

N,K = map(int, input().split())
arr = [None] + [tuple(map(int, input().split())) for _ in range(N)]

dp = [[0]*(K+1) for _ in range(N+1)]

for n in range(N):
    w,v = arr[n+1]
    for k in range(K+1):
        if k>=w:
            dp[n+1][k] = max(dp[n][k], dp[n][k-w] + v)
        else:
            dp[n+1][k] = dp[n][k]

print(max(dp[-1]))

자바

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[][] dp = new int[N+1][K+1];
        for (int n=0; n<N; n++) {

            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            for (int k=0; k<K+1; k++) {
                if (k>=w) {
                    dp[n+1][k] = Math.max(dp[n][k], dp[n][k-w] + v);
                } else{
                    dp[n+1][k] = dp[n][k];
                }
            }
        }

        int answer = 0;
        for (int k=0; k<K+1; k++) {
            answer = Math.max(answer, dp[N][k]);
        }
        System.out.println(answer);
    }
}

---

코멘트

• 사실 2차원 DP에서 1차원으로 줄일 수 있다.
• dp를 K+1 무게 크기만큼 초기화됐을 때, 각 쿼리가 들어올 때 마다 dp를 훑어주면 1차원 dp로도 가능하다.
  • 1차원 DP를 사용하는 경우에는 역순으로 훑어줘야한다.
  • 앞에서부터 dp 배열을 최대값으로 채우는데, 동작중인 쿼리에서 갱신된 최대값이 또 최대값을 갱신하는 문제가 발생한다.

  for k in range(K,w-1,-1):
      dp[k] = max(dp[k], dp[k-w] + v); 

  • 이런식으로 역방향으로 탐색해줘야 중복 업데이트가 발생하지 않는다.