[Gold II] 헌책방 - 5550

문제 링크

성능 요약

메모리: 23536 KB, 시간: 300 ms

분류

다이나믹 프로그래밍, 누적 합, 정렬

제출 일자

2024년 12월 13일 23:43:43

문제 설명

상근이가 살고있는 도시에는 헌책방이 있다. 데이트 비용을 점점 감당할 수 없게된 상근이는 집에 있는 책을 헌책방에 팔려고 한다. 각 책에는 기준 가격이 정해져있고, 헌책방은 이 가격으로 매입한다.

헌책방은 책을 소설, 만화, 잡지등 10개의 장르로 분류한다. 장르는 1부터 10까지 번호가 매겨져 있다. 이 가게는 같은 장르의 책을 한 번에 매입할 때, 고가로 매입해 준다.

같은 장르의 책을 T권 매입할 때, 책 한 권 당 매입 가격이 기준 가격보다 T-1원 높아진다. 예를 들어, 같은 장르에서 기준 가격이 100원, 120원, 150원인 책을 한 번에 헌책방에 판다면, 매입 가격은 102원, 122원, 152원이 된다.

상근이는 내일 데이트를 가기 위해서 가지고 있는 책 N권 중 K권을 팔려고 한다.

책 N권의 기준 가격과 장르 번호가 주어졌을 때, 총 매입 가격의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 책의 개수 N과 파려고 하는 책의 수 K가 주어진다. (2 ≤ N ≤ 2000, 1 ≤ K < N)

둘째 줄부터 N개 줄에는 상근이가 가지고 있는 책의 기준 가격 Ci와 장르 Gi가 공백으로 구분되어 주어진다. (1 ≤ Ci ≤ 105, 1 ≤ Gi ≤ 10)

출력

첫째 줄에 총 매입 가격의 최댓값을 출력한다.

문제 풀이

상당히 어려웠다... 아이디어가 매우 중요한데

• 선택하는 책 카테고리를 늘려가기
• 선택하는 책 수를 늘려가기
• 최대값을 dp에 저장 ( dp[i][j]는 i종류 j개일 때 최대가격을 의미)

코드

Java 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, K, bookCnt, categorySize;
    static long dp[][];
    static ArrayList<Integer>[] books;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_5550_헌책방/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        dp = new long[11][K + 1];

        books = new ArrayList[11];
        for (int i = 0; i < 11; i++) {
            books[i] = new ArrayList<>();
        }

        int price, category;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            price = Integer.parseInt(st.nextToken());
            category = Integer.parseInt(st.nextToken());
            books[category].add(price);
        }

        for (int i = 1; i <= 10; i++) {
            Collections.sort(books[i], Collections.reverseOrder());

            ArrayList<Integer> tmp = new ArrayList<>(books[i]);

            for (int j = 1; j < books[i].size(); j++) {
                books[i].set(j, books[i].get(j) + books[i].get(j - 1));
            }

            for (int j = 1; j < books[i].size(); j++) {
                books[i].set(j, books[i].get(j) + j * (j + 1));
            }
        }
        
        int res = 0;
        bookCnt = 0;
        for (int i = 1; i <= 10; i++) {
            categorySize = books[i].size();
            /* 헷갈린부분
             * 똑같은 개수로 진행되어야하므로 이전에 골랐든 안골랐든 cnt만큼 추가
             * 예를 들면 앞 종류에서 2개 뒷종류에서 3개랑 같은 선상에서 뒷종류만 5개를 고른경우가 비교되어야하므로 min(K, size)하면안됨! 놓치는 경우생김
             */
            int leftAmount = Math.min(K, bookCnt + categorySize);
            for (int j = 0; j <= leftAmount; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int k = 1; k <= categorySize; k++) {
                    if (j >= k) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k] + books[i].get(k - 1));
                }
            }
            bookCnt = Math.min(bookCnt + categorySize, K);
        }

        bw.write(String.valueOf(dp[10][K]));
        bw.flush();
        bw.close();
        br.close();
    }
}

---

C++ 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int N, K;
    cin >> N >> K;
    vector<vector<int>> books(11);
    vector<vector<long long>> dp(11, vector<long long>(K + 1));

    for (int i = 0; i < N; i++) {
        int price, category;
        cin >> price >> category;
        books[category].push_back(price);
    }

    for (int i = 1; i <= 10; i++) {
        sort(books[i].rbegin(), books[i].rend());
        // sort(books[i].begin(), books[i].end(), greater<int>());
        // sort(books[i].begin(), books[i].end(),
        //      [](int a, int b) { return a > b; });

        vector<int> tmp = books[i];
        for (int j = 1; j < books[i].size(); j++) {
            books[i][j] = books[i][j] + books[i][j - 1];
        }
        for (int j = 1; j < books[i].size(); j++) {
            books[i][j] = books[i][j] + j * (j + 1);
        }
    }

    int bookCnt = 0;
    for (int i = 1; i <= 10; i++) {
        int categorySize = books[i].size();
        int leftAmount =
            min(K, bookCnt + categorySize);  // 고를 수 있는 최대 수

        for (int j = 0; j <= leftAmount; j++) {
            dp[i][j] = dp[i - 1][j];
            for (int k = 1; k <= categorySize; k++) {
                if (j >= k) {
                    dp[i][j] =
                        max(dp[i][j], dp[i - 1][j - k] + books[i][k - 1]);
                }
            }
        }
        bookCnt = min(bookCnt + categorySize, K);
    }
    cout << dp[10][K] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}