[BOJ 26969] Bribing Friends

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

26969번: Bribing Friends

 

- 문제 요약

 

Bessie는 N(1<=N<=2000)명의 친구가 있습니다.

친구들과 함께 영화를 보러 가고싶지만, 친구들은 그다지 가고 싶어 하지 않습니다.

Bessie는 그런 친구들에게 돈과 아이스크림 콘 뇌물을 주려 합니다.

N개의 줄에 각 친구에 대한 입력 Pi, Ci, Xi가 들어옵니다.

Pi는 친구의 인기 지수 (Bessie는 이 점수의 합을 최대화 하길 원합니다), Ci는 친구들이 받길 원하는 돈, Xi는 친구들이 받길 원하는 아이스크림 콘의 개수 (아이스크림 콘을 Xi개 받으면 친구들은 Ci를 1 줄여줍니다)

Bessie가 함께 영화를 보러 가는 친구들의 인기 지수를 최대화 할 수 있도록 도와주세요! 

 

 

- 알고리즘 정리

 

가벼운 냅색 문제입니다.

https://en.wikipedia.org/wiki/Knapsack_problem

Knapsack problem - Wikipedia

Bessie가 i번째 친구에게 뇌물을 주는 경우에 선택적으로 아이스크림 콘을 사용할 수 있다는 점을 유의하며 풀었습니다.

 

 

- 코드 작성

 

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

#define MAX 2001
int n,a,b,dp[MAX][MAX*2];
vector<array<int,3>>v(MAX);

void f(int &aa,int bb){
	if(bb>aa){
		aa=bb;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>a>>b;
	v.resize(n);
	for(auto &[x,p,c]:v){
        cin>>p>>c>>x;
    }
    sort(v.begin(),v.end());
	memset(dp,-1,sizeof(dp));
	dp[0][a+b]=0;
	for(int i=0;i<n;i++){
		auto [x,p,c]=v[i];
		for(int j=0;j<=a+b;j++){
			if(dp[i][j]==-1){
				continue;
			}
			f(dp[i+1][j],dp[i][j]);
			if(j-c*x>=a){
				f(dp[i+1][j-c*x],dp[i][j]+p);
			}
			else if(j>a){
				int w=c-(j-a)/x;
				if(a-w>=0){
					f(dp[i+1][a-w],dp[i][j]+p);
				}
			}
			else if(j<=a&&j-c>=0){
				f(dp[i+1][j-c],dp[i][j]+p);
			}
		}
	}
	cout<<*max_element(dp[n],dp[n]+a+b+1);
}

코드 제출 결과

문제 풀고나서 글 쓰면서 느낀 건데, 말이 좋아서 뇌물이지... 거의 친구비 상납 ㅋㅋㅋㅋㅋ;;;

 

불쌍한 베시....