취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24229번 문제인 모두싸인 출근길이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/probelm/24229

필요한 관찰을 먼저 해보자.

(1) 어떤 두 판자가 같은 점을 공유한다면, 해당 두 판자는 하나의 긴 판자로 생각해도 무방함을 관찰하자.

(2) 위의 관찰에 따라 같은 점을 공유하는 판자들을 하나의 큰 판자로 바꿔 생각하면, 주어진 문제는 판자들이 서로 겹치지 않게 모델링이 가능하다.

(3) 어떤 판자에서 (판자로 연결되지 않은) 다른 판자로 점프해 이동할 수 있다면, 해당 판자의 가장 왼쪽 끝점으로 점프하는 것이 항상 이득이다. 다음 점프로 도달할 수 있는 거리를 최대화할 수 있기 때문이다.

이 두 관찰에 따라, 출발점(0)부터 시작해 점프를 통해 도착할 수 있는 좌표의 범위와 도달할 수 있는 거리(도착할 수 있는 최대 좌표)의 값을 관리하면서 판자들을 차례대로 살펴 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<pair<int, int>> vec, seg;
int tmpL, tmpR;
int ans, reachable;

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

	cin >> N;
	while (N--) {
		int L, R; cin >> L >> R;
		vec.emplace_back(L, R);
	}
	sort(vec.begin(), vec.end());
	for (auto &p : vec) {
		if (tmpR < p.first) {
			seg.emplace_back(make_pair(tmpL, tmpR));
			tmpL = p.first, tmpR = p.second;
		}
		else tmpR = max(tmpR, p.second);
	}
	seg.emplace_back(make_pair(tmpL, tmpR));

	for (auto &p : seg) {
		if (reachable < p.first) break;
		ans = max(ans, p.second);
		reachable = max(reachable, p.first + (p.second - p.first) * 2);
	}

	cout << ans;
}

(BOJ Random Defense #1)