1. 장애물을 x 좌표 순으로 정렬. 도착지점의 Y좌표와 걸린 길이(y축 이동만 고려)를 저장하는 set을 선언 후, {startY, 0} 를 추가
2. 장애물을 하나씩 꺼내며, 그 장애물에 걸리는 원소만 set에서 꺼내고 하나씩 위로갔을때 거리와 아래로 갔을때 거리를 계산
이때, 꺼낸 것이 10개여도 장애물의 위 아래 각각에서 최소거리가 걸리는 것만 set에 다시 저장 -> 즉, 10개 여도 2개만 저장됨.
3. 2에서 검사한 원소는 set에서 제거한다.
4. 모든 장애물을 상대로 하면, 이제 최소거리를 구하고, 그때의 y좌표를 저장하고, 출력하면 됨.
코드
#include <iostream>#include <algorithm>#include <vector>#include <set>using namespace std;struct Line { long long x; long long yl; long long yh; bool operator < (Line b) { return x == b.x ? yl < b.yl : x < b.x; }};int n, starty, endx;vector<Line> line;set<pair<long long, long long>> minY;long long min(long long a, long long b) { return a < b ? a : b;}int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> starty >> endx; for (int i = 0; i < n; i++) { long long a, b, c; cin >> a >> b >> c; line.push_back({ a,b,c }); } sort(line.begin(), line.end()); minY.insert({ starty, 0 }); for (int i = 0; i < n; i++) { vector<pair<long long, long long>> temp; set<pair<long long, long long>>::iterator s = minY.lower_bound({ line[i].yl, -200000000000000 }); set<pair<long long, long long>>::iterator e = minY.upper_bound({ line[i].yh, 200000000000000 }); long long up = 20000000000000, down = 200000000000000; for (set<pair<long long, long long>>::iterator j = s; j != e; ++j) { up = min(up, (line[i].yh - j->first) + j->second); down = min(down, (j->first - line[i].yl) + j->second); } minY.erase(s, e); minY.insert({ line[i].yh, up }); minY.insert({ line[i].yl, down }); } long long result = 20000000000000; vector<int> resultY; for (set<pair<long long, long long>>::iterator s = minY.begin(); s != minY.end(); s++) { result = min(result, s->second); } for (set<pair<long long, long long>>::iterator s = minY.begin(); s != minY.end(); s++) { if (result == s->second) { resultY.push_back(s->first); } } cout << result + endx<< "\n"; cout << resultY.size() << " "; for (int i = 0; i < resultY.size(); i++) { cout << resultY[i] << " "; }}