[BOJ 15337 // C++] Starting a Scenic Railroad Service

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

 

이번에 볼 문제는 백준 15337번 문제인 Starting a Scenic Railroad Service이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/15337 

15337번: Starting a Scenic Railroad Service

이 문제는 policy-1과 policy-2의 두 문제를 해결해야하는 문제이다.

policy-1은 각 구간에 대해서 "이 구간과 겹치는 다른 구간의 수"가 가장 많은 구간을 찾으면 되고, policy-2는 가장 많은 사람들이 겹쳐 예약한 구간을 찾는 것으로 해결이 가능하다. 각 policy는 O(N)의 시간에 구할 수 있다.

 

policy-1은 이 구간과 "겹치지 않는" 구간의 수를 세어 전체 구간의 개수에서 빼주는 것으로 계산할 수 있다.

구체적으로, 한 구간을 [L, R]이라고 하면 겹치지 않는 구간 [x,y]는 y<=L이거나 R<=x를 만족하게 된다.

따라서, prefix sum을 이용해서 각 index보다 작은 y의 개수 배열과 각 index보다 큰 x의 개수 배열을 전처리하고 각 구간을 한번씩 살피면 O(N)으로 policy-1을 해결할 수 있다.

 

policy-2는 간단히 1차원 imos법을 통해 O(N)으로 해결할 수 있다.

 

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

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

int imos[100001];
int psum[100001];
int ssum[100001];
pair<int, int> seg[200000];

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

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		imos[x]++, imos[y]--;
		psum[y]++, ssum[x]++;
		seg[i] = { x,y };
	}

	int ans1 = 0, ans2 = 1000000007;
	for (int i = 1; i < 100001; i++) {
		imos[i] += imos[i - 1];
		ans1 = max(ans1, imos[i]);
	}
	for (int i = 0; i < 100000; i++) {
		psum[i + 1] += psum[i];
	}
	for (int i = 99999; i > -1; i--) {
		ssum[i] += ssum[i + 1];
	}

	for (int i = 0; i < N; i++) {
		int x = seg[i].first, y = seg[i].second;
		int tmp = psum[x] + ssum[y];
		ans2 = min(ans2, tmp);
	}

	cout << N - ans2 << ' ' << ans1;
}