[백준] 마라톤 1

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

10655번: 마라톤 1

우선 문제부터 간단하게 요약하면, 

 

출발지에서 도착지까지 체크포인트를 순서대로 거쳐서 가는데, 한 체크포인트를 건너뛰고 도착지로 갈 때, 최단 경로가 몇이 나오는지를 구해야 합니다.

 

<Solution>

각각의 체크포인트 사이의 구간을 구하고, 한 구간을 건너 뛰었을 때의 구간사이의 거리를 구해서 

 

얼마나 줄어드는지를 계산해서 최대로 줄어드는 경우를 구하는 방식으로 계산하였습니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <cstdlib>

using namespace std;

#define MAXN ((int)1e5)

int N;
int X[MAXN + 10];
int Y[MAXN + 10];
int dist_1[MAXN + 10];
int dist_2[MAXN + 10];

void InputData(){
    cin >> N;
    for (int i=0; i<N; i++){
        cin >> X[i] >> Y[i];
    }
}

int solution(){
    // 직접 한칸간격 두칸간격 모두 계산
    for(int i =0; i<N-1; i++){
        dist_1[i] = abs(X[i]-X[i+1]) + abs(Y[i]-Y[i+1]);
    }
    for(int i = 0; i<N-2; i++){
        dist_2[i] = abs(X[i]-X[i+2]) + abs(Y[i]- Y[i+2]);
    }

    // total sum dist_1
    int t_s = 0;
    for(int i = 0; i<N-1; i++){
        t_s += dist_1[i];
    }

    int m = -1;
    for(int i = 0; i<N-2; i++){
        m = max(m, dist_1[i] + dist_1[i+1] - dist_2[i]);
    }

    return t_s - m;



}

int main(){
    int ans = -1;

    InputData();

    ans = solution();

    cout << ans << endl;
    return 0;
}