백준 10655 - 마라톤 (C++)

 

 

소들은 N개의 체크포인트를 거쳐 목적지까지 도달한다고 한다. 그 과정에서 딱 1번 체크포인트를 스킵할 수 있는데, 체크포인트를 스킵하고 이동했을 때 나올 수 있는 최소 이동거리를 구하면 된다. 

 

문제 풀이

풀이는 간단하다.

 

하나도 스킵하지 않고, 출발지부터 목적지까지 도달하기 위한 거리를 먼저 구해준다.

이후, 각 체크포인트를 3개씩 검사하며, 특정 체크포인트를 스킵했을 때 얼만큼 거리가 절약되는지의 최대값을 구한다.

이후, 전체 거리에서 절약되는 거리의 최대값을 빼주면 된다.

 

예를 들어, 1~5번까지 스킵하지 않고 가는 거리가 20이라고 해보자.

 

2번 체크포인트를 스킵하게 되면, 절약되는 거리는 [(1->2->3)의 거리 - (1->3)의 거리] 가 될 것이다.

3번 체크포인트를 스킵하게 되면, 절약되는 거리는 [(2->3->4)의 거리 - (2->4)의 거리] 가 될 것이다.

 

이 과정을 게속 거쳐서, 절약되는 거리의 최대값을 구해준다.

 

하나의 체크포인트만 스킵할 수 있다면, 당연히 가장 거리가 절약되는 체크포인트를 스킵하는 것이 최단거리가 될 것이기 때문에 구해준 최대값을 전체 거리에서 빼주면 된다.

 

풀이 코드

 

int NumOfCP = 0;
std::cin >> NumOfCP;

std::vector<std::pair<int, int>> CPs(NumOfCP);
for (int i = 0; i < NumOfCP; i++)
{
    std::cin >> CPs[i].first;
    std::cin >> CPs[i].second;
}

 

먼저, 체크포인트에 대한 정보를 입력받아주었다.

int GetDist(const std::pair<int, int>& _Start, const std::pair<int, int>& _End)
{
    return std::abs(_Start.first - _End.first) + std::abs(_Start.second - _End.second);
}

 

두 체크포인트 사이의 거리를 구하는 함수도 정의해주었다.

 

int MaxGap = 0;

for (int i = 0; i < NumOfCP - 2; i++)
{
    int NormalDistance = GetDist(CPs[i], CPs[i + 1]) + GetDist(CPs[i + 1], CPs[i + 2]);
    int SkipDistance = GetDist(CPs[i], CPs[i + 2]);

    int Gap = NormalDistance - SkipDistance;

    if (Gap > MaxGap)
    {
        MaxGap = Gap;
    }
}

 

이후, 반복문을 돌며, 각 체크포인트를 스킵하였을 때 절약할 수 있는 거리의 최대값을 갱신해주었다.

 

int SumDist = 0;

for (int i = 0; i < NumOfCP - 1; i++)
{
    SumDist += GetDist(CPs[i], CPs[i + 1]);
}

 

다음은, 하나도 스킵하지 않았을 때의 전체 거리를 구해주었다.

 

SumDist -= MaxGap;

std::cout << SumDist;

return 0;

 

전체 거리에서 절약되는 거리를 빼준 뒤, 해당 값을 출력해주면 문제 해결이다.

 

코드 전문

#include <iostream>
#include <vector>
#include <cmath>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int GetDist(const std::pair<int, int>& _Start, const std::pair<int, int>& _End)
{
    return std::abs(_Start.first - _End.first) + std::abs(_Start.second - _End.second);
}

int main()
{
    Init();

    int NumOfCP = 0;
    std::cin >> NumOfCP;

    std::vector<std::pair<int, int>> CPs(NumOfCP);
    for (int i = 0; i < NumOfCP; i++)
    {
        std::cin >> CPs[i].first;
        std::cin >> CPs[i].second;
    }

    int MaxGap = 0;

    for (int i = 0; i < NumOfCP - 2; i++)
    {
        int NormalDistance = GetDist(CPs[i], CPs[i + 1]) + GetDist(CPs[i + 1], CPs[i + 2]);
        int SkipDistance = GetDist(CPs[i], CPs[i + 2]);

        int Gap = NormalDistance - SkipDistance;
        
        if (Gap > MaxGap)
        {
            MaxGap = Gap;
        }
    }

    int SumDist = 0;

    for (int i = 0; i < NumOfCP - 1; i++)
    {
        SumDist += GetDist(CPs[i], CPs[i + 1]);
    }

    SumDist -= MaxGap;

    std::cout << SumDist;

    return 0;
}