마라톤 1 (백준 10655)

안녕하세요. 오늘은 마라톤을 뛸거예요.

문제

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

아이디어

sum을 정직하게 끝까지 갔을 때 거리라고 합시다.
i번째를 스킵하면 (i-1부터 i)를 빼고 (i부터 i+1)을 빼고 (i-1부터 i+1)을 더하는것과 같습니다. 계산을 해서 최솟값을 구해주면 됩니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define pll pair <ll,ll>
using namespace std;

ll dis(pll A, pll B)
{
    return abs(A.first - B.first) + abs(A.second - B.second);
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, i, x, y;
    vector <pll> v;

    cin >> N;
    for (i = 1; i <= N; i++)
    {
        cin >> x >> y;
        v.push_back({ x,y });
    }

    ll sum = 0;
    for (i = 1; i < N; i++) sum += dis(v[i - 1], v[i]);

    ll mn = 2e9;
    for (i = 1; i < N - 1; i++)
        mn = min(mn, sum - dis(v[i - 1], v[i]) - dis(v[i], v[i + 1]) + dis(v[i - 1], v[i + 1]));
    cout << mn;
}

감사합니다.