[ boj : 23559 ] 밥

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

23559번: 밥

해설 : 일단 전 솔직하게 말씀드려서 이거 실버 문제는 아닌것 같아요..ㅠㅠㅠ

잘하시는 분들 난이도평 보면 골드급은 아니라고 하시는데 전 아무리 못해도 골드4 이상이라고 생각합니다.

 

과연 대다수의 사람들이 이 문제를 처음 봤을때 '관찰'을 통해 '아이디어'를 끄집어 낼 수 있을지 잘 모르겠네요...

 

문제 해설하겠습니다.

 

먼저 문제를 읽고 우리가 생각할 수 있는 부분은 어떤 코너를 선택해야될까???입니다.

그러나 이 선택부분이 결코 함부로 판단을 할 수는 없습니다. 당장 5000원짜리를 우선적으로 고르자니 나중에 1000원인 놈이 더 이득인 경우가 발생할 수 있고 그 반대도 성립할 수 있기 때문입니다.

 

그래서 전 근본적으로 1000원짜리를 5개 선택하는 것보다 5000원 짜리 하나를 선택하는 것이 더 이득이라면,

이는 1000짜리 5개를 선택한 것을 버리고 5000원 짜리 한개를 선택하는 것이 맞는 판단이겠죠.

 

이를 실현하기 위해 먼저 우리는 모든 메뉴를 그냥 1000원짜리만 선택했다고 가정을 해보고 시작하는 것입니다.

그리고 5000원짜리와 비교를 해주면서 5000원짜리 고르는 것이 더 이득이면 바꾸면 되겠죠?

 

이를 선별하기 위해 우린 '잘' 선택을 해주어야 하는데, 정렬을 해줍시다. 어떻게?

(5000원 가치) - (1000원 가치) 순으로요. 선택할때마다 4000원씩 더 빼주면 되겠죠.

 

더 이상 남아있는 돈이 4000원 보다 적거나 (5000원 가치)-(1000원 가치) 가 0보다 적을때까지 이를 반복해주면 됩니다.

 

#include<bits/stdc++.h>

using namespace std;

vector<pair<int, int>> v;

int main()
{
	int n, x;
	cin >> n >> x;
	v.resize(n);

	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> v[i].first >> v[i].second;
		sum += v[i].second;
        x-=1000;
	}
	sort(v.begin(), v.end(), [](const pair<int, int > a, const pair<int, int> b) {
		return abs(a.first - a.second) > abs(b.first - b.second);
		});
	
	for (int i = 0; i < n; i++) {
		if (x >= 4000 && v[i].first - v[i].second >= 0) {
			x -= 4000;
			sum += v[i].first - v[i].second;
		}
	}
	cout << sum;
}