[BOJ] 18234 - 당근 훔쳐 먹기

1. 문제 해석

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

18234번: 당근 훔쳐 먹기

• 텃밭에 N개의 당근을 심을 수 있다.(1 <= N <= 200,000)
• 각 당근은 맛을 가지고 있다. 또한, 각각의 영양제를 가지고 있다.
• i 당근은 처음 wi 의 맛을 가지고, 영양제를 통해 pi 만큼 맛을 증가시킬 수 있다.(1 <= wi <= pi <= 100,000,000)
• 오전에 밭을 관리한다. 각 당근 i 에 대해 당근 i 가 자리에 없다면 당근 i 를 자리에 심고, 있다면 영양제를 준다.
• 오후에는 당근을 먹을 수 있다. 최대 1개를 먹을 수 있고 먹지 않을 수도 있다.
• T일 동안 먹을 수 있는 당근 맛의 합의 최대 값을 구해야 한다.(N <= T <= 100,000,000)

2. 접근방법

• pi 가 클 수로 나중에 먹는 것이 유리하다.
• 예를 들어, wa = 1, pa = 8, wb = 1, pb =4 이고 3일과 5일에 하나씩 먹는 다고 해 보자. 3일에 a 당근을 먹고 5일에 b 당근을 먹었을 경우 17 + 17 = 34 이다. 반면 3일에 b 당근을 먹고 5일에 a 당근을 먹었을 경우 9 + 33 = 42이다. 따라서 pi 가 큰 당근을 나중에 먹는 것이 유리하다.
• 문제의 조건에서 영양제를 통해 얻을 수 있는 맛 pi 는 처음 당근의 맛 wi 보다 크거나 같다.
• 따라서 중간에 먹지 않고 가능한 오래 영양분을 주고 당근을 먹는 것이 유리하다.
• 결과적으로 N개의 당근을 한 번씩 먹는 것이 최선의 방법이다.

 

3. 주의할 점

• 당근의 맛을 계산할 때 32비트 정수 변수(int)로 계산할 경우 오버플로우가 발생할 수 있다.

 

4. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long N, T;
vector<pair<long, long>> vec;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> T;

	for (int i = 0; i < N; i++) {
		long long w, p;
		cin >> w >> p;
		vec.push_back({ p, w });
	}
	sort(vec.begin(), vec.end());

	long long ans = 0;
	for (int i = 0; i < N; i++) {
		long long val = (i + T - N) * vec[i].first + vec[i].second;
		ans += val;
	}	

	cout << ans << '\n';

	return 0;
}