[Solved.ac] G5 평범한 베낭 해결 과정(Java)

 문제 링크

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

 

---

 

 문제를 보고 dp로 어떻게 접근을 해야 할지 많이 고민함. 그러다가 베낭이 담을 수 있는 최대 무게를 1부터 [k] 일 때와 주어진 물건을 
1개 ~ n개일 때를 각각 나눠 반복문으로 비교 작업 수행

int[][] dp = new int[물건 배열 length + 1][k + 1];

for(int index = 1; index < dp.length; index++) {
    for(int 현재무게 = 1; 현재무게 <= k; 현재무게++) {
        dp[index][현재무게] = /* 비교 로직 수행 */
    }
}

 그러고 문제에서 요구하는 상황은 dp[물건배열.length][k]에 값이 저장되어 있기 때문에 이 값을 반환하면 됨.

해결 완료 후 성능 요약

---

 전체 코드

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

public class Main {

    static int weight;
    static int[] weights, values;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int count = Integer.parseInt(st.nextToken());
        weight = Integer.parseInt(st.nextToken());
        weights = new int[count+1];
        values = new int[count+1];

        for(int i = 1; i <= count; i++) {
            st = new StringTokenizer(br.readLine());
            weights[i] = Integer.parseInt(st.nextToken());
            values[i] = Integer.parseInt(st.nextToken());
        }
        //배낭에 물건을 담을만한 기준을 선택하지
        /*
            물건이 2개만 있을 때
            담을 수 있는 무게 내에서 가치가 더 큰 것.
            dp
         */
        int[][] dp = new int[count + 1][weight + 1];

        for(int t = 1; t < dp.length; t++) {
            for(int w = 1; w < dp[t].length; w++) { //현재 무게
                if(weights[t] > w) {
                    dp[t][w] = dp[t-1][w];
                } else {
                    //물건을 담을 떄와 담지 않을 때 비교,
                    // 담을 때는 해당 무게가 추가 되기 전의 가치에서 담을 무게의 가치를 합한다.
                    dp[t][w] = Math.max(dp[t-1][w], dp[t-1][w-weights[t]]+values[t]);
                }
            }
        }

        bw.write(""+dp[count][weight]);
        bw.flush();
        br.close();
        bw.close();

    }
}

---

 정리

• 문제를 어떻게 분할할 것인지 충분히 생각해보자.