"백준 10655번: 마라톤 1" 문제를 풀어보았다!

🤔 문제 설명

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

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

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

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

✅ 나의 풀이

처음에는 DFS 문제인줄 알고 너무 어렵게 생각했는데 이것도 수학 문제였다. 건너뛰지 않았을 때의 거리와 건너뛰었을 때의 거리를 비교해가면서 최소거리를 구했다.

#include <iostream>
#include <vector>
using namespace std;


int main() {
    int N;
    cin >> N;

    vector<pair<int, int>> points(N);
    for (int i = 0; i < N; ++i) {
        cin >> points[i].first >> points[i].second;
    }

    // 초기값 설정
    int totalDistance = 0;
    for (int i = 1; i < N; ++i) {
        totalDistance += abs(points[i].first - points[i - 1].first) + abs(points[i].second - points[i - 1].second);
    }

    int minDistance = totalDistance;
    for(int i=1; i<N-1;i++) {
        int jumpDistance = abs(points[i+1].first - points[i-1].first) + abs(points[i+1].second - points[i-1].second);
        int diff = abs(points[i + 1].first - points[i].first) + abs(points[i + 1].second - points[i].second)
            + abs(points[i].first - points[i - 1].first) + abs(points[i].second - points[i-1 ].second);

        minDistance = min(minDistance, totalDistance+jumpDistance-diff);
    }

    cout << minDistance << endl;
   
}

➡️ 무작정 풀지말고 좀 더 생각하고 풀자!