[BOJ 12865] 평범한 배낭

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

백준 12865 평범한 배낭 – 1차원 DP 풀이 (Java)

---

📌 문제 요약

• 물건 N개가 있고 각 물건은 무게(W)와 가치(V)를 가진다.
• 배낭은 최대 K 무게까지 담을 수 있다.
• 각 물건은 한 번만 선택 가능(0/1 배낭)
• 담을 수 있는 가치의 최댓값을 구한다.

---

💡 핵심 아이디어

이 문제는 전형적인 0/1 knapsack문제이다.

 

[DP 정의]

dp[w] = 무게 w까지 담을 수 있을 때 얻을 수 있는 최대 가치

 

[중요한 포인트]

• 같은 물건을 여러 번 쓰면 안 됨
• 따라서 dp 배열을 역순으로 순회해야 함

---

❗ 왜 역순으로 순회해야 할까?

만약 정방향(w → k)으로 순회하면, 현재 물건을 여러 번 사용하는 상태가 된다.

• 정방향 ❌ → 무한 배낭
• 역방향 ⭕ → 0/1 배낭

---

🧠 코드 전체 (Java)

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

class Main{
    public static void main(String[] args) throws IOException{
        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[][] items = new int[n][2];
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            items[i][0] = Integer.parseInt(st.nextToken());    // 무게
            items[i][1] = Integer.parseInt(st.nextToken());    // 가치
        }
        
        int[] dp = new int[k + 1];
        
        for(int[] item : items){
            int w = item[0];
            int v = item[1];
            
            // 역순 순회 (중복 선택 방지)
            for(int i = k; i >= w; i--){
                dp[i] = Math.max(dp[i], dp[i - w] + v);
            }
        }
        
        System.out.println(dp[k]);
    }
}