[백준/BOJ] 백준 2543번 : 초고속철도

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

2543번: 초고속철도

cache[index]에 'index번째 로봇부터 고려하여 구하는 처리장치 부착 경우의 수' 를 저장하여 다이나믹 프로그래밍(DP)을 이용해 문제를 해결했다.

 

index번째 로봇부터 고려하는 처리장치 부착 경우의 수는 index번째에 처리 장치를 부착하는 경우와 부착하지 않는 경우로 나누어서 경우의 수를 고려했으며, index번째에 처리 장치를 부착하지 않는 경우에는 index번째 이후의 로봇에서 index 로봇 범위에 겹치는 로봇에는 처리장치를 모두 부착해야 하므로 index번째 로봇 범위에 겹치는 이후 로봇들에는 경우의 수를 따질 필요가 없고, index번째 로봇과 겹치는 부분이 없는 이후 로봇부터 확인하도록 하였다.

 

이때 index번째 로봇과 겹치는 부분이 없는 로봇은 index번째 로봇 범위의 끝지점보다 큰 시작지점을 가진 로봇들로, upper_bound를 이용하여 구했다.

 

코드

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

int n;
vector<pair<int, int>> robot;
vector<long long> cache(100005, -1); //[index] = index번째 로봇부터 고려하여 구하는 처리장치 부착 경우의 수

//index번째 로봇부터 고려하는 처리장치 부착 경우의 수를 구한다
long long Solve(int index) {

	//모두 확인했을때 (경우의 수 하나 발견)
	if (index == n) {
		return 1;
	}

	long long& ret = cache[index];

	if (ret != -1) {
		return ret;
	}

	ret = 0;

	//result1 = index번째에 처리장치를 부착할때의 경우의 수
	//index번째 이후 로봇에 처리장치를 부착할지, 부착하지 않을지 영향이 없다
	//즉 그냥 index+1번째 로봇부터 고려하는 처리장치 부착 경우의 수를 구하면 된다
	long long result1 = (Solve(index + 1) + 20070713) % 20070713;

	//result2 = index번째에 처리장치를 부착하지 않을때의 경우의 수
	//index번째 이후의 로봇에서 index 로봇 범위에 겹치는 로봇에는 처리장치를 모두 부착해야 한다
	//즉 index번째 로봇 범위에 겹치는 이후 로봇에는 처리장치를 모두 부착해야 되므로 그 로봇들은 경우의수를 따질 필요가 없고, index번째 로봇과 겹치는 부분이 없는 이후 로봇부터 확인한다
	//index번째 로봇과 겹치는 부분이 없는 로봇은 index번째 로봇의 끝지점보다 큰 시작지점을 가진 로봇들이다
	int upper_bound_index = upper_bound(robot.begin(), robot.end(), make_pair(robot[index].second, -1)) - robot.begin();
	long long result2 = (Solve(upper_bound_index) + 20070713) % 20070713;

	ret = (result1 + result2 + 20070713) % 20070713;

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int left, right;
		cin >> left >> right;

		robot.push_back(make_pair(left, right));
	}

	sort(robot.begin(), robot.end());

	cout << Solve(0);

	return 0;
}