[BAE/<JOON> 문제풀이] 20928. 걷는 건 귀찮아

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

20928번: 걷는 건 귀찮아

서론

라인 스윞 기본 문제 ( 그리디 )

---

풀이

어떤 인력거의 출발 도착 위치가 s, e이고 모든 인력거들이 출발점을 기준으로 정렬되어 있다면, 이 인력거로 갈아탈 수 있는 이전 인력거는 출발점이 e보다 작아야 한다.

조건을 만족하는 인력거들을 찾아가며 환승 횟수를 갱신해 답을 구할 수 있다.

그리고 풀이를 쓰면서 생각난건데, 검사한 인력거들 중 도착 위치가 가장 큰 인력거를 우선으로 검사하는 게 더 빠를 것 같다. 새로운 인력거의 도착 위치가 기존 도착 위치보다 작다면 검사할 필요가 없다. 이 문제 다시 풀어봐야겠다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct line {
	int s, e;
};
bool cmp(line a, line b) {
    return a.s < b.s;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m; vector<line> arr(n + 1); vector<int> dp(n + 1, 21e8);
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].s;
	}
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].e; arr[i].e += arr[i].s;
	}
    sort(arr.begin() + 1, arr.end(), cmp);
	dp[1] = 0;  
	if (arr[1].e >= m) {
		cout << 0; return 0;
	}
	int mn = 21e8;
	for (int i = 1; i <= n; i++) {
		int k = lower_bound(arr.begin() + i + 1, arr.end(), arr[i].e, [](line p, int e) { return p.s <= e; }) - arr.begin() - i - 1;	
		for (int j = i + 1; j <= i + k; j++) {
			if (arr[j].e >= m) {
				mn = mn < dp[i] + 1 ? mn : dp[i] + 1;
			}
			if (dp[j] < dp[i] + 1) continue;			
			dp[j] = dp[i] + 1;
		}
	}
	cout << (mn == 21e8 ? -1 : mn);
	return 0;
}