개요

[링크]백준 15748번: Rest Stops

입력
The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest stop and the tastiness of the grass there.

It is guaranteed that $r_F > r_B$, and $0 < x_1 < \dots < x_N < L$.
Note that $r_F$ and $r_B$ are given in seconds per meter!

출력
A single integer: the maximum total tastiness units Bessie can obtain.

대충 파머와 파머 트레이너 베시가 하이킹 가는데,
베시는 파머의 트레이너라서 속도가 더 빠름.
그러나 베시는 지구력이 딸려서 중간에 쉬어야 하지만
트레이너라서 뒤쳐질 순 없다.

총 하이킹거리는 직선거리로 생각하고,
파머와 베시의 1미터 가는데 걸리는 초를 입력값으로 준다.

그 후 하이킹 도중에 있는 쉬는 스팟의 정보를 준다.
스팟 장소값와 쉬었을 때
얼마만큼 만족도(?)를 얻을 수 있는지 수치값을 준다.

그래서 베시가 얻을 수 있는 최대 만족도를 구하라.
라는 문제다.

접근 방식

• 만족도가 제일 높은 곳에서 많이 쉬어야
  최대 만족도를 구할 수 있으니, 만족도 기준으로 정렬을 한다.

• 제일 만족도가 높은 곳에 왔을 때, 속도와 그 장소의 거리를 이용해 해당 장소에 방문하는 둘의 시간 차를 구한다.

• 해당 시간 차만큼 만족도를 곱하고 답 변수에 더해준다.

코드

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

using namespace std;

vector<pair<int, int>> v;
bool comp(pair<int, int>a, pair<int, int>b) {			//tastiness가 더 큰순대로 비교, tastiness가 같다면 시간이 더 적은순대로 나열
	if (a.second != b.second)
		return a.second > b.second;
	else
		return a.first < b.first;

}

void input(int& L, int& N,long long& Rf,long long& Rb) {			//입력받는 함수
	int Xi = 0, Ci = 0;
	cin >> L >> N >> Rf >> Rb;
	for (int i = 0; i < N; i++) {
		cin >> Xi >> Ci;
		v.push_back(make_pair(Xi, Ci));
	}


}
void solution(const int& L,const int& N,const long long& Rf,const long long& Rb) {
	long long ans = 0, curRestDistance = 0;;								//답, 쉰장소
	sort(v.begin(), v.end(), comp);
	for (int i = 0; i < N; i++) {
		if (curRestDistance < v[i].first) {											//만족도대로 정렬을 했으므로, 그다음 만족도가 높은곳을 이미 지나쳤을 수도 있으므로
																					//지나쳤다면 무시해야한다.

			long long differDistance = v[i].first - curRestDistance;				//전에 쉰 장소에서 베시가 존을 기다렸다 같이 출발하므로
																					//시간차이 계산할 때 전에 쉰 곳과 현재 장소의 위치만큼만 계산해야한다

			long long differSecond = differDistance* Rf - differDistance* Rb;		//제일 tastiness가 높은 곳에 도달 했을 때, 그 둘의 시간 차이
			ans += differSecond * v[i].second;
			curRestDistance = v[i].first;
		}
	}
	cout << ans;
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(0);
	int L = 0, N = 0;
	long long Rf = 0, Rb = 0;

	input(L,N,Rf,Rb);
	solution(L,N,Rf,Rb);
}				

문풀후생

중요한 건 m/s를 주는게 아닌 s/m이다.
문제에서도 강조했지만 자세히 안보고 한번 틀렸다.

그리고 만족도 높은 곳에서 둘의 시간차와 만족도를 계산한 후,
그 다음 만족도 높은 곳에서 둘의 시간차 계산할 때,
전에 쉰 곳에서 둘이 같이 출발하는 걸 꼭 기억해야 한다!!