[백준][C++] 18234: 당근 훔쳐 먹기

문제 링크: https://www.acmicpc.net/problem/18234

 

좀 생각해봐야 하는 문제인데요, 입력 조건에 힌트가 있습니다.

\(N \leq T\)이고, \(w_i \leq p_i\)이라는 점을 곰곰히 생각해보면 T-N일동안 아무것도 먹지 않고 기다리기만 하는게 항상 이득이라는 점을 알 수 있습니다.

그 다음 T-N일이 지난 후 N개의 당근을 하루에 하나씩 뽑아 먹으면 되는데, 나무 자르기 문제와 비슷하게 영양제를 맞았을 때 맛이 늘어나는 정도가 적은 것부터 먹으면 됩니다.

 

문제가 좀 어려워보이지만, 입력조건을 좀 생각해보면 쉽게 풀 수 있는 그리디 문제였습니다.

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


typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n, t;
	cin >> n >> t;

	vector<pair<ll, ll>> carrots(n);
	for (auto& [p, w] : carrots)
		cin >> w >> p;

	sort(carrots.begin(), carrots.end());

	ll sum = 0;
	for (int i = 0; i < n; ++i)
		sum += carrots[i].second + (carrots[i].first * (t-n+i));

	cout << sum << '\n';

	return 0;
}