백준 5550번 (JOI 2011년 2번), 헌책방 풀이

문제

백준 5550번

풀이

전형적인 DP (누적합+그리디) 문제로 볼 수 있습니다.

 

"dp[i] = i권을 선택했을 때 만들 수 있는 최대 가격" 으로 점화식을 세워줍시다.

 

모든 장르에 대해서 i번째 책까지 골랐을 때, 해당 장르의 j개의 책을 추가로 고르는 경우로 DP table을 채워주면 됩니다.

 

시간복잡도는 $O(GN^2)$이 되는데, N이 1000이고 G가 10이므로 G는 무시할만한 수준입니다.

따라서, DP의 시간복잡도는 $O(N^2)$이 됩니다.

 

DP의 조건이 좀 까다로워 구현하는데 고생했던 것 같습니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

int dp[2001];
vector<int> book[11], sum[11];

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		book[b].push_back(a);
	}

	for (auto &vec : book) sort(vec.begin(), vec.end(), greater<>());
	for (int i = 1; i <= 10; i++) {
		auto vec = book[i];

		sum[i].resize(vec.size());
		for (int j = 0; j < vec.size(); j++) {
			sum[i][j] = (j ? sum[i][j - 1] : 0) + vec[j];
		}
	}

	for (const auto &books : sum) 
		for (int base_cnt = k; base_cnt >= 0; base_cnt--) 
			for (int j = 1; j <= books.size(); j++) {
				if (base_cnt + j > k) break;
				if (!base_cnt || dp[base_cnt]) 
					dp[base_cnt + j] = max(dp[base_cnt + j], dp[base_cnt] + books[j - 1] + (j - 1) * j);
				
			}
		
	

	cout << dp[k];
}