[BOJ 5550] 헌책방

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

5550번: 헌책방

 

- 문제 요약

 

상근이가 살고 있는 도시에는 헌책방이 있다.

각 책에는 기준 가격이 정해져 있고, 헌책방은 이 가격으로 매입한다.

헌책방은 책을 소설, 만화, 잡지등 10개의 장르로 분류한다. (1부터 10까지)

이 가게는 같은 장르의 책을 한 번에 매입할 때, 고가로 매입해 준다.

같은 장르의 책을 T권 매입할 때, 책 한 권 당 매입 가격이 기준 가격보다 T-1원 높아진다.

상근이는 가지고 있는 책 N권 중 K권을 팔려고 한다.

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

 

 

- 알고리즘 정리

 

dp[x] : x권을 선택했을 때 만들 수 있는 최대 가격

dp[cnt+j]=max(dp[cnt+j],dp[cnt]+w[j-1]+(j-1)*j)

=> j개의 책을 추가로 고르는 경우에 현재 dp table의 값이 최대인지 확인한 후, 갱신 + 값 채워주기

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 2001
int n,k,dp[MAX];
vector<int>v[11],sum[11];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k;
	for(int i=0;i<n;i++){
		int a,b;
		cin>>a>>b;
		v[b].push_back(a);
	}
	for(auto &w:v){
		sort(w.begin(),w.end(),greater<>());
	}
	for(int i=1;i<=10;i++){
		auto w=v[i];
		sum[i].resize(w.size());
		for(int j=0;j<w.size();j++){
			sum[i][j]=(j?sum[i][j-1]:0)+w[j];
		}
	}
	for(auto &w:sum){
		for(int cnt=k;cnt>=0;cnt--){
			for(int j=1;j<=w.size();j++){
				if(cnt+j>k){
					break;
				}
				if(!cnt||dp[cnt]){
					dp[cnt+j]=max(dp[cnt+j],dp[cnt]+w[j-1]+(j-1)*j);
				}	
			}
		}
	}
	cout << dp[k];
}

코드 제출 결과