BOJ_12865 평범한 배낭

• TOC {:toc}

이 글은 백준 온라인 저지의 12865번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.06 (Python)

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

N, K = map(int, input().split())
Vs = [[0] * (K + 1) for _ in range(N)]

for i in range(N):
    W, V = map(int, input().split())

    for j in range(1, K + 1):
        if j < W:
            Vs[i][j] =  Vs[i - 1][j]
        else:
            Vs[i][j] = max(Vs[i - 1][j], Vs[i - 1][j - W] + V)

print(Vs[N - 1][K])

아이디어 & 풀이

1부터 K까지 각 무게에서 들 수 있을는 최대 가치합을 저장한다.

• W를 인덱스로, 최대 가치 합 V를 값으로 갖는 리스트를 구성한다.

• 입력받은 W보다 큰 W값에 대해서 V를 비교하면서 입력한 V가 더 크면 교체한다.

  for i > W:
      V vs F[i] vs F[i-W] + V
  

디버그

• 각 원소가 바로바로 변하니까 이전 단계를 별도로 저장해주어야 한다.
  • Vs[3]의 값을 앞에서 변경하고 Vs[7]의 값을 정할 때 Vs[3] + Vs[4]를 비교하면 Vs[3]은 변한 상태이므로 제대로 된 최댓값을 계산할 수 없다.
  • 현재 상태에서 이전의 Vs값들을 유지하려면 이를 별도로 저장해주어야 한다.
  • Vs를 이차원 배열로 초기화하고 업데이트 때마다 다음 배열에 저장한다.

피드백

• max를 계산할 때 Vs[i - 1]에 V를 더한 값이 항상 V보다 크거나 같기 때문에 V는 고려할 필요가 없다.
• 마지막에 Vs의 max를 계산하지 않고 K를 출력하는게 더 빠르다. (어차피 K의 값이 최댓값이다)

2022.04.03 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [NK, ...items] = input;
const [N, K] = NK.split(" ").map(Number);
bag = { 0: 0 }; // weight: value

function main() {
    const new_bag = { 0: 0 };

    items.forEach((item) => {
        const [W, V] = item.split(" ").map(Number);
        for (let [w, v] of Object.entries(bag)) {
            w = parseInt(w);
            if (w + W <= K) {
                if (bag[w + W]) new_bag[w + W] = Math.max(bag[w + W], v + V);
                else new_bag[w + W] = v + V;
            }
        }
        bag = new_bag;
    });

    return Math.max(...Object.values(bag));
}

console.log(main());

디버그

• 또 입력받을 때 trim() 안 적어서 틀렸다.

피드백

• input 입력 받을 때 아예 map으로 전부 다 숫자로 변환하고 하는 게 깔끔했을 것 같다.

참고 답안 1

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
KnapSack = {0: 0}
for _ in range(N):
    W, V = map(int, input().split())
    tmp = {}
    # KanpSack(배낭) 딕셔너리 안의 각 key(무게, w)와 value(가치, v)에 대해서
    for w, v in KnapSack.items():
        # 현재 아이템과 입력받은 무게의 합(w + W)이 K를 넘지 않고
        # 현재 아이템과 입력받은 가치의 합(v + V)이 두 무게를 합친 것의 가치 최댓값(KanpSack[w + W])보다 크면
        if w + W <= K and v + V > KnapSack.get(w + W, 0): 
            # tmp에 해당 무게의 가치 최댓값을 현재 값으로 지정한다.
            tmp[w + W] = v + V

    # KnapSack을 tmp로 업데이트한다.
    KnapSack.update(tmp)

# KnapSack의 value(가치) 중에서 최댓값을 출력한다.
print(max(KnapSack.values()))

아이디어 & 풀이

기본적인 과정은 위의 답과 비슷하다.

리스트 대신 딕셔너리를 사용해 현재 KanpSack 안에 존재하는 아이템에 대해서만 계산한다. 반복을 최소화할 수 있다.

• get의 디폴트 값을 이용해 해당 값을 가져오지 못하면 0을 가져오도록 한다.
• 02-5 딕셔너리 자료형: Key로 Value얻기(get) by 점프 투 파이썬
• get() by Python Documentation

변하는 부분만 tmp를 먼저 구성한 뒤 tmp로 기존의 KanpSack을 업데이트해서 사용하는 메모리를 최소화한다.

• 25.1 딕셔너리 조작하기 by 코딩도장
• update() by Python Documentation

참고 답안 2

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").trim().split("\n");

const bag = input.map((str) => str.split(" ").map(Number));
const [N, K] = bag.shift();

function solution() {
  const matrix = Array(K + 1).fill(0);

  bag.forEach(([w, v]) => {
    for (let i = K; i >= w; i -= 1) {
      matrix[i] = Math.max(matrix[i], matrix[i - w] + v);
    }
  });

  return matrix[K];
}

console.log(solution());

풀이 분석해서 적기