BOJ_12865 : 평범한 배낭

👉 문제링크

---

---

🔸 문제 분석 🔸

• 가치의 총 합이 최대가 되도록 배낭에 물건을 담고, 그 값을 출력한다.
• 전형적인 dp문제이다.
  • 가방의 무게 제한을 0부터 k까지 늘려가며 최적값을 누적해 간다.
  • 한 물건에 대해, 넣었을때와 안넣었을때 어느 값이 더 최적인지 비교해 가며 누적해 간다.
  • 무게 제한이 k이면서 모든 물건이 고려된 최종 결과를 출력한다.
• dp를 2차원 배열로 구현한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public 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());
        Obj[] objs = new Obj[n+1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            objs[i] = new Obj(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }

        int[][] dp = new int[n+1][k+1];

        for (int i = 1; i <= n; i++) {      // 물건 순회
            for (int j = 1; j <= k; j++) {  // 배낭 제한 무게 순회
                if (objs[i].w <= j) {       // 현재 물건 넣을 수 있음
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-objs[i].w]+objs[i].v); // 넣었을 때와 넣지 않았을때 비교
                }
                else {                      // 현재 물건 넣을 수 없어서 이전 최적값
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[n][k]);
    }

    private static class Obj{
        int w, v;

        public Obj(int w, int v) {
            this.w = w;
            this.v = v;
        }
    }
}

🔸 코드 해석 🔸

• 물건들을 하나씩 고려해본다.
• 배낭 무게 제한을 1부터 k까지 늘리며 dp배열을 채워간다.
  • 물건의 수나 배낭 무게 제한이 0이면 dp배열의 값은 0이다.
  • 만약 제한 무게보다 물건의 무게가 작다면(해당 물건을 배낭에 넣을 수 있다면),
    물건을 넣었을때와 넣지 않았을 때를 비교해서 더 큰 값을 저장한다.
    • 물건을 넣지 않았을 때의 최적값은 직전 물건의 같은 배낭 무게 제한에 값이므로 dp[i-1][j]이다.
    • 물건을 넣었을때의 최적값은, 물건을 넣고 무게 제한 남은 부분에 최적값을 넣은 상태이다.
      (물건을 넣음 : objs[[i].v , 남은 공간의 최적값 : dp[i-1][ j - ojbs[i].w] )
  • 현재 물건을 넣을 수 없으면, 직전 물건의 최적값을 그대로 적는다. ( dp[i-1][j] )
• 같은 배낭 무게 제한에서 모든 물건이 고려된 최적값인 dp[n][k]를 출력한다.

---

🔸 end 🔸

• 2차원 dp를 그림을 그려서 많이 풀이하는 것 같다.
• 전형적인 유명한 dp문제라는데, 엄청 신선한 충격을 받았다. (어떻게 이런 풀이를)