[BOJ 2836]
문제 바로가기 : https://www.acmicpc.net/problem/2836
문제 설명은 위 링크에서 확인해주시길 바랍니다.
solutionPermalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //2836 | |
| #include <iostream> | |
| #include <string> | |
| #include <cstring> | |
| #include <cstdio> | |
| #include <vector> | |
| #include <algorithm> | |
| using namespace std; | |
| #define INF (1e9+1) | |
| #define MAXSIZE 500001 | |
| typedef long long ll; | |
| typedef vector<int> vi; | |
| typedef vector<vector<int>> vvi; | |
| typedef vector<pair<int, int>> vii; | |
| typedef pair<int, int> ii; | |
| vector<pair<ll, ll>> lines; | |
| int main() { | |
| cin.tie(nullptr); | |
| cout.tie(NULL); | |
| ios_base::sync_with_stdio(false); | |
| int n; int m; cin >> n >> m; | |
| lines.resize(n); | |
| for (int i = 0; i < n; i++) { | |
| ll fir, sec; cin >> fir >> sec; | |
| //역으로 가는 방향만 | |
| if (fir > sec) { | |
| swap(fir, sec); | |
| lines[i] = { fir, sec }; | |
| } | |
| } | |
| sort(lines.begin(), lines.end()); | |
| ll left = -INF, right = -INF, reverse_len = 0; | |
| for (int i = 0; i < lines.size(); i++) { | |
| if (right < lines[i].first) { | |
| reverse_len += right - left; | |
| left = lines[i].first; | |
| right = lines[i].second; | |
| } | |
| else { | |
| right = max(right, lines[i].second); | |
| } | |
| } | |
| reverse_len += right - left; | |
| reverse_len *= 2; | |
| ll ans = m + reverse_len; | |
| cout << ans; | |
| return 0; | |
| } |
reviewPermalink
BOJ 2170에서 썼던 아이디어를 응용하는 문제다.
상근이는 0에서 M까지 이동하는데 이 방향을 순방향이라고 하자.
순방향으로 가는 승객은 신경쓸 필요가 없다. M으로 가면서 중간에 내려주면 되기 때문에 추가로 이동하지 않는다.
신경쓸 부분은 역방향으로 가는 승객이다. 원래 갈 거리가 M이었는데 승객이 역방향으로 가면 그 거리의 2배를 이동해야 한다.
근데 역으로 가는 승객들이 많다고 생각해볼 필요가 있다. 이 승객들의 경로가 겹칠 수도 있다!
이렇게 역방향으로 이동하는 승객들의 경로만 모아놓고 정렬하면 BOJ 2170와 다를게 없다.
역으로 이동하는 거리를 구한 후, 2배를 해주고 M에 더해주면 답이 된다.
댓글남기기