BOJ 2543 초고속철도

* BOJ 2543 초고속철도

[분류: 다이나믹 프로그래밍]

[풀이]

  인접한 로봇끼리는 반드시 통신이 가능해야 한다는 점을 유심히 보자.

  만약 어떤 로봇 a가 b, c, d, w와 겹치는 상황을 생각해보자.

    1. [a에 설치하는 경우] 나머지 b,c,d,w,에 설치할 수도 있고 안할 수도 있다.

    2. [a에 설치하지 않는 경우] b,c,d,w에 모두 통신을 설치해야만 한다.

[순서도]

  1. 먼저 구간 시작 좌표를 기준으로 로봇들을 정렬하자. 정렬하는 이유는 시작 좌표가 낮은 로봇을 기준으로 설치하느냐 마느냐를 결정하여 이후에 있는 로봇에 영향을 미치는 데에 있어 계산하기 용이하기 때문이다.

  2. 오름차순으로 방문하며 현재 p번째 로봇에 대해 통신장비를 설치할지말지를 결정해야 한다.

  3. 설치한다면 p번째 로봇 이후의 로봇들에 대한 통신장비를 설치할지말지 여부에 아무런 영향을 끼치지 않는다.

  4. 설치하지 않는다면 이 로봇과 연관된 모든 로봇은 반드시 설치해야만한다. 따라서 p번째 로봇 끝 구간 이후의 로봇들은 영향을 받지않으므로 끝 구간 이후의 로봇 중 시작구간이 가장 가까운 로봇부터 다시금 부분문제를 풀면 된다.

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MOD = 20070713, MAX_N = 1e5;
using ll = long long;
pair<int, int> pos[MAX_N];
int N, dp[MAX_N];
int rec(int p) {
	if (p == N) return 1;
	int& ret = dp[p];
	if (ret != -1) return ret;
	return ret = (rec(p + 1) + rec(upper_bound(pos + p, pos + N, make_pair(pos[p].second, -1)) - pos)) % MOD;
}
int main() {
	memset(dp, -1, sizeof dp);
	int i;
	scanf("%d", &N);
	for (i = 0; i < N; i++) scanf("%d%d", &pos[i].first, &pos[i].second);
	sort(pos, pos + N);
	printf("%d", rec(0));
	return 0;
}