Q 5550 헌책방

💡 문제 요약 및 분석

상근이가 가진 책 N개 중에서 K개를 파는데, 같은 장르의 책을 T권 팔 때는 책 한 권당 매입 가격이 기준 가격보다 T-1원 높아진다. 예를 들어 같은 장르에서 100원, 120원, 150원인 책을 헌책방에 판다면 각각 102, 122, 152원이 되는 것이다. 상근이가 가진 책 정보가 주어졌을 때 총 매입 가격의 최댓값을 구하면 된다.

💡 알고리즘 설계

🔥 처음에는 이차원 배열[장르][책]을 만들고 정렬한 후 누적합하는거라고 생각했는데 하다보니 dp 를 이용해야 할 것 같다는 생각이 들어서 힌트를 찾아봤는데 그래도 모르겠어서 정답을 확인하고 풀었다.

💡 코드

import java.util.*;

public class Main {

    static int read() throws Exception {
        int c, n = 0;
        while((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int n = read();
        int k = read();
        List<Integer>[] books = new ArrayList[11];
        for (int i = 0; i < 11; i++) books[i] = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int price = read();
            int genre = read();
            books[genre].add(price);
        }

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

        // 각 장르별로 반복
        for (int g = 0; g <= 10; g++) {
            List<Integer> genreList = books[g];
            if (genreList.isEmpty()) continue;

            // 책 가격을 내림차순으로 정렬
            Collections.sort(genreList, Collections.reverseOrder());
            int m = genreList.size();

            // 누적합 생성
            int[] prefix = new int[m + 1];
            for (int i = 0; i < m; i++) {
                prefix[i + 1] = prefix[i] + genreList.get(i);
            }

            // dp[] 배열을 복제해서 임시 dp 배열을 만든다.
            int[] ndp = Arrays.copyOf(dp, dp.length);

            // i: 이 장르에서 몇 권을 고를지 (0권 ~ m권)
            for (int i = 1; i <= m; i++) {
                int total = prefix[i] + i * (i - 1);
                for (int j = k; j >= i; j--) {
                    ndp[j] = Math.max(ndp[j], dp[j - i] + total);
                }
            }
            dp = ndp;
        }
        System.out.println(dp[k]);
    }
}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(n * k)	O(n + k)

💡 느낀점 및 기억할 정보

배낭 풀이 (knapsack)

이와 같은 풀이를 배낭 풀이(knapsack)라고 하는데, dp를 계산하는 수식은 답을 봐도 이해하기가 쉽지 않아서 한줄씩 풀어서 정리해보았더니 이해가 갔다… knapsack 풀이의 핵심은 임시 배열을 활용하는 것과, 역순으로 풀어야 한다는 점이다 !!

[ 표준 입력 ]
장르 1 : 14
장르 2 : 14, 13, 11, 8
장르 3 : 16, 12

[ 누적합 배열 ]
장르 1 : [0, 14]
장르 2 : [0, 14, 27, 38, 46]
장르 3 : [0, 16, 28]

[ 연산 시작 ]
[ 장르 1 ]
dp = [0, 0, 0, 0, 0]
ndp = [0, 14, 14, 14, 14] 한 권 판매

[ 장르 2 ]
dp = [0, 14, 14, 14, 14]
ndp = [0, 16, 30, 30, 30] 한 권 판매
ndp = [0, 16, 30, 44, 44] 두 권 판매

[ 장르 3 ]
dp = [0, 16, 30, 44, 44]
ndp = [0, 16, 30, 44, 58] 한 권 판매
ndp = [0, 16, 30, 45, 59] 두 권 판매
ndp = [0, 16, 30, 45, 60] 세 권 판매
ndp = [0, 16, 30, 45, 60] 네 권 판매

문제에서 제시한 k = 4 이므로, dp[4] = 60 이다.

직접 풀었을 때 같은 장르의 책을 k 권 구매하는 것까진 할 수 있었는데 여러 장르의 조합을 어떻게 구현해야 하는지 몰라 애를 먹었다. 정답 코드에서는 ndp[4] 의 경우, 한 장르로만 계산했을 때의 최댓값 ndp[4] 와 다른 장르와 조합했을 때의 최댓값 dp[2] + prefix[2] + 보너스 를 비교하도록 만들어서 모든 조합을 비교할 수 있도록 했다. 여기서 내가 놓쳤던 점은 다른 장르에서 2권을 팔았으면 이번 장르에서 최대로 팔 수 있는게 2권이라는 점을 코드에 넣었어야 했고 (j - i 부분), dp 계산을 역순으로 해야 바른 답이 나온다는 점이었다.