백준 10655 - 마라톤 1

 

 

문제 설명

농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.

마라톤 코스는 N (3 ≤ N ≤ 100000) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한개를 몰래 건너뛰려 한다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.

젖소 박승원이 체크포인트 한개를 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?

참고로, 젖소 마라톤 대회는 서울시내 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다. 즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)

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

 

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 체크포인트 중 하나를 제거하여 가장 짧은 경로를 만들어야 한다.

경로의 길이는 $|x1 - x2| + |y1 - y2|$이다.

 

N이 100,000이기 때문에 $N^2$은 사용할 수 없다.

 

문제를 풀기 위해서는 각 체크포인트마다 이전과 다음 거리를 계산하여 제거했을 때 가장 이득이 되는 지점을 제거하면 된다.

즉, 입력을 받는 과정에서 전체 체크포인트의 거리를 미리 계산한 후 하나의 체크포인트를 제거했을 때 줄일 수 있는 비용을 최대로 만들면 된다.

 

우선, 전체 체크포인트의 거리를 구하는 것은 간단하다.

입력을 받은 뒤, 이전 체크포인트와의 거리를 계산하면 된다.

vector<pair<int, int>> CheckPoints;

int total = 0;

for (int i = 0; i < N; i++)
{
    int y, x;

    cin >> y >> x;
    CheckPoints.push_back({ y,x });
    if (i == 0) continue;

    total += CalcDist(CheckPoints[i], CheckPoints[i - 1]);
}

 

이후, 2번째 체크포인트부터 N-1번째 체크포인트까지 해당 체크포인트를 제거했을 때, 얼마나 거리를 줄일 수 있는지 확인한다.

int skip = 0;
for (int i = 1; i < N - 1; i++) {
    pair<int, int> prev = CheckPoints[i - 1];
    pair<int, int> cur = CheckPoints[i];
    pair<int, int> next = CheckPoints[i + 1];

    int dist = CalcDist(prev, cur) + CalcDist(cur, next);
    int skippedDsit = CalcDist(prev, next);
    skip = max(skip, dist - skippedDsit);
}

dist에서 skippedDist를 빼는 이유는 이미 total에는 dist의 값이 더해져 있고, 만약 이번 체크포인트가 없어진다면 그만큼을 빼주어야 하기 때문이다. 

 

즉, a+b는 이미 total에 더해져있다.

그리고 이번 체크포인트가 없어지면 c만큼 거리가 든다.

따라서, total에서 a+b를 빼고 c를 더해주어야 한다.

지금은 없어지는 거리를 구하는 것이기 때문에 반대로 (a+b)-c만큼이 없어지는 거리가 된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <set>

using namespace std;

int N;

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    vector<pair<int, int>> CheckPoints;

    int total = 0;

    for (int i = 0; i < N; i++)
    {
        int y, x;

        cin >> y >> x;
        CheckPoints.push_back({ y,x });
        if (i == 0) continue;

        total += CalcDist(CheckPoints[i], CheckPoints[i - 1]);
    }

    int skip = 0;
    for (int i = 1; i < N - 1; i++) {
        pair<int, int> prev = CheckPoints[i - 1];
        pair<int, int> cur = CheckPoints[i];
        pair<int, int> next = CheckPoints[i + 1];

        int dist = CalcDist(prev, cur) + CalcDist(cur, next);
        int skippedDist = CalcDist(prev, next);
        skip = max(skip, dist - skippedDist);
    }

    cout << total - skip;

	return 0;
}

---