BOJ 15748 Rest Stops

BOJ 15748 Rest Stops

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

요약

으.. 영어 문제 간단하게 해석해보자면

Farmer John과 Bessie가 등산을 한다, Jhon과 Bassie가 1미터를 등반하는데 걸리는 시간은 rf, rb로 주어지고 항상 rf < rb이다.

John은 출발하면 계속 등반하고, Bassie는 중간중간에 쉬면서 풀을 먹는데 풀을 먹으면서 쉴 수 있는 점과 1시간당 먹을 수 있는 풀의 양은 주어진다.

이때 Bassie가 John에게 뒤처지지 않으면서 먹을 수 있는 가장 많은 풀의 양을 구하는 문제이다.

입력값으로 등산로의 길이, 휴식 지점, John과 Bassie의 1미터를 등반하는데 걸리는 시간, 휴식 지점 당 1시간 동안 먹을 수 있는 풀의 양이 주어진다.

풀이

어떤 식으로 해야 가장 많은 풀을 먹을 수 있을지 꽤 고민했다.

원초적으로 생각해 보면 풀을 가장 많이 먹을 수 있는 데에 직행해서 John이 도착할 때까지 가장 많이 먹는 게 풀을 가장 많이 먹을 수 있을 것이다.

하지만 그 뒤에는 어떤 지점에서 우선적으로 쉬면서 풀을 먹어야 할지 고민했다.

이런 식으로 지점당 먹을 수 있는 풀의 양을 그래프로 나타냈을 때 이런 식으로 증가하고 있는 경우는 젤 높은 부분에서 다 먹는 게 맞다.

하지만 이렇게 풀의 양이 감소하는 그래프에서는 버리고 갈수록 더 손해기 때문에 지점마다 다 들려서 풀을 섭취하는 게 이득이다.

이런 식으로 지점이 존재한다면 두 번째에 있는 지점보다 세 번째에 지점에 도착해서 풀을 섭취하는 것이 더 이득이다.

즉 도착지점부터 거꾸로 봤을 때 점점 증가하는 부분에서 쉬면서 풀을 섭취해 주면 최대의 풀을 먹을 수있다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, int>>q;
long long L, N, rf, rb, w, d, ans, chk[1000001];
int main() {
	cin >> L >> N >> rf >> rb;
	for (int i = 0; i < N; i++) {
		cin >> w >> d;
		q.push_back({ w,d });
	}
	long long big = -1e9;
	for (int i = N - 1; i >= 0; i--) {
		if (big < q[i].second) {
			chk[q[i].first] = 1;
			big = q[i].second;
		}
	}
	long long p = 0;
	for (int i = 0; i < N; i++) {
		if (chk[q[i].first] == 1) {
			ans += ((rf*(q[i].first - p)) - (rb * (q[i].first - p)))*q[i].second;
			p = q[i].first;
		}
	}
	cout << ans << "\n";
}