BOJ - 마라톤 1 (C++)

문제 출처: https://www.acmicpc.net/problem/10655

문제 난이도

Silver 2

문제 접근법

N 범위가 십만이기 때문에 N^2으로 해결할 수 없다.
그래서 일일이 계산하기 보단 체크 포인트 건너뛰고 전 후로 가는 거리가 작을 수록 좋다.
-> 체크 포인트 합쳐서 더해진 거리 - 체크 포인트 건너뛰고 더해진 거리 최대값을 구한 후에 total 거리에서 뺀다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int,int>> a;

int dist(pair<int, int> a, pair<int, int> b) {
	return abs(a.first- b.first) + abs(a.second - b.second);
}

int main() {
	int N;
	cin >> N;
	int sx, sy;
	cin >> sx >> sy;
	int total = 0;
	a.push_back({ sx,sy });
	for (int i = 0; i < N-1; i++) {
		int x, y;
		cin >> x >> y;
		a.push_back({ x,y });
		total += dist({ sx,sy }, { x,y });
		sx = x;
		sy = y;
	}
	pair<int, int> pre, cur, next;
	int skip = 0;
	for (int i = 1; i < N - 1; i++) {
		pre = a[i - 1];
		cur = a[i];
		next = a[i + 1];
		int d = dist(pre, cur) + dist(cur, next);
		int straight = dist(pre, next);
		skip = max(skip, d - straight);
	}
	cout << total - skip;
	return 0;
}