문제 링크 : 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";
}
'BOJ' 카테고리의 다른 글
BOJ 1629 곱셈 (0) | 2022.03.12 |
---|---|
BOJ 11047 동전 0 (0) | 2022.03.10 |
BOJ 13904 과제 (0) | 2022.03.10 |
BOJ 2212 센서 (0) | 2022.03.10 |
BOJ 11000 강의실 배정 (0) | 2022.03.10 |
댓글