BOJ12920 평범한배낭2(Java)

---

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

태그 : dp, 배낭 문제

---

사고과정

가장 쉬운 풀이는 n M K 해서 모든 경우 구하는 것이겠지만... 공간/시간복잡도 모두 아웃이다.

여기서 그럼 시간을 줄이려면 결국 M이나 K 탐색 시간을 줄이는 것인데...

아무리 고민해도 떠오르지 않았다. 그래서 Gemini의 도움을 받았다.

---

아이디어

아이디어는 K개의 물건을 Log N에 모두 탐색한 효과를 내는 것이다.

예를들어 무게 1짜리 물건이 13개가 있다고 하면..

러프한 풀이대로면 1번물건이 하나인 경우, 두 개인 경우, ...13개인 경우를 센다. -> O(N)이 된다.

이를 1개, 2개, 4개, 6개 묶음으로 생각하고 푸는것이다.

1개는 그냥 넣는다 치고, 두 개인 경우를 보면,

dp[3]이 두 번의 탐색만에 갱신이 가능해졌다. dp[3] = 현재 무게2 + dp[1].

4개인 경우를 보면,

dp[7]이 갱신 가능하다. dp[3] + 현재 무게4
dp[6] 역시 갱신 가능하다. dp[2] + 현재 무게4
dp[5] = dp[1] + 현재무게4

그 이외에도 k<=13인 모든 경우가 표현이 가능해진다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int N, M, ans;
    static List<Stuff> stuff = new ArrayList<>();

    static int [] dp;

    static class Stuff {
        int V, C, K;
        public Stuff(int V, int C, int K) {
            this.V = V;
            this.C = C;
            this.K = K;
        }
    }

    public static void solve() {
        for (int i = 0; i < N; i++) {
            int v = stuff.get(i).V;
            int c = stuff.get(i).C;
            int k = stuff.get(i).K;

            for(int count = 1; k > 0; count *= 2) {
                int usage = Math.min(count, k);

                int weight = v * usage;
                int value = c * usage;

                for(int j = M; j >= weight; j--) {
                    dp[j] = Math.max(dp[j], dp[j - weight] + value);
                    ans = Math.max(ans, dp[j]);
                }
                k -= usage;
            }

        }
    }

    public static void main(String args[]) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine().trim());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dp = new int [M + 1];

        for (int i = 0; i < N; ++i) {
            st = new StringTokenizer(br.readLine().trim());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            stuff.add(new Stuff(v, c, k));
        }
        solve();
        System.out.println(ans);

    }
}

---

후기

k개의 탐색을 Log(K)로 줄이는 아이디어가 굉장히 인상적이였다.

이 아이디어를 꼭 써먹을 날이 오길