[백준 10655] 마라톤 1 (C#, C++) - soo:bak

문제 링크

10655번 - 마라톤 1

설명

N개의 체크포인트를 순서대로 이동할 때, 첫 번째와 마지막을 제외한 중간 체크포인트 하나를 건너뛸 수 있습니다. 맨해튼 거리로 측정했을 때 최소 총 이동 거리를 구하는 문제입니다.

접근법

먼저, 모든 체크포인트를 순서대로 방문했을 때의 총 거리를 계산합니다. 인접한 두 점 사이의 맨해튼 거리를 모두 더합니다.

다음으로, 각 중간 체크포인트를 건너뛰었을 때 절약되는 거리를 계산합니다. i번째 체크포인트를 건너뛰면 원래 거리에서 이전-현재-다음 구간의 거리를 빼고, 이전-다음 직접 이동 거리를 더합니다. 이 차이가 절약량이 됩니다.

이후, 모든 중간 체크포인트에 대해 절약량의 최댓값을 구하고, 총 거리에서 이 값을 빼면 최소 이동 거리가 됩니다.

시간 복잡도는 O(N)입니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static int Dist((int x, int y) a, (int x, int y) b) {
      return Math.Abs(a.x - b.x) + Math.Abs(a.y - b.y);
    }

    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var pts = new List<(int x, int y)>(n);
      for (var i = 0; i < n; i++) {
        var s = Console.ReadLine()!.Split();
        pts.Add((int.Parse(s[0]), int.Parse(s[1])));
      }

      var total = 0;
      for (var i = 0; i < n - 1; i++)
        total += Dist(pts[i], pts[i + 1]);

      var bestSave = 0;
      for (var i = 1; i < n - 1; i++) {
        var d1 = Dist(pts[i - 1], pts[i]) + Dist(pts[i], pts[i + 1]);
        var d2 = Dist(pts[i - 1], pts[i + 1]);
        var save = d1 - d2;
        if (save > bestSave)
          bestSave = save;
      }

      Console.WriteLine(total - bestSave);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vp;

int dist(pii a, pii b) {
  return abs(a.first - b.first) + abs(a.second - b.second);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vp p(n);
  for (int i = 0; i < n; i++)
    cin >> p[i].first >> p[i].second;

  int total = 0;
  for (int i = 0; i < n - 1; i++)
    total += dist(p[i], p[i + 1]);

  int bestSave = 0;
  for (int i = 1; i < n - 1; i++) {
    int d1 = dist(p[i - 1], p[i]) + dist(p[i], p[i + 1]);
    int d2 = dist(p[i - 1], p[i + 1]);
    bestSave = max(bestSave, d1 - d2);
  }

  cout << total - bestSave << "\n";

  return 0;
}