백준 10655번 [마라톤 1](C++) -yes6686- 티스토리

백준 문제 풀이: 10655번 [마라톤 1]

---

문제 링크: https://www.acmicpc.net/problem/10655

문제 설명:

마라톤 경로에서 한 체크포인트를 건너뛰었을 때의 최소 이동 거리를 계산하는 문제입니다. 체크포인트들은 2차원 평면 위에 있으며, 인접한 두 체크포인트 간의 거리(맨해튼 거리)가 주어집니다.

---

문제 해결 코드

#include <iostream>
#include <cmath>  // abs() 함수 사용
#include <algorithm>  // min() 함수 사용
using namespace std;

pair<int, int> arr[100001]; // 체크포인트 좌표 저장
int dis[100001];               // 각 구간의 거리 저장

int main() {
    ios::sync_with_stdio(false); // 입출력 속도 향상
    cin.tie(NULL);

    int n;
    cin >> n; // 체크포인트 개수 입력

    int totalDis = 0; // 총 이동 거리 초기화
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first >> arr[i].second; // 각 체크포인트 좌표 입력
    }

    // 체크포인트 간 거리 계산 및 총 거리 합산
    for (int i = 1; i < n; i++) {
        int dx = abs(arr[i].first - arr[i - 1].first);
        int dy = abs(arr[i].second - arr[i - 1].second);
        dis[i] = dx + dy; // 현재 구간 거리
        totalDis += dis[i]; // 총 거리 누적
    }

    int minDis = totalDis; // 최소 이동 거리 초기화

    // 한 체크포인트를 건너뛰었을 때의 최소 거리 계산
    for (int i = 2; i < n; i++) {
        int dx = abs(arr[i].first - arr[i - 2].first); // 건너뛴 체크포인트의 거리
        int dy = abs(arr[i].second - arr[i - 2].second);
        int skipDist = dx + dy; // 건너뛰었을 때의 거리
        minDis = min(minDis, totalDis + skipDist - dis[i] - dis[i - 1]);
    }

    cout << minDis << '\n'; // 최소 이동 거리 출력
    return 0;
}

---

코드 설명

위 코드는 주어진 경로에서 한 체크포인트를 건너뛰었을 때의 최소 이동 거리를 계산합니다. 주요 로직은 다음과 같습니다:

1. 입력 처리: 체크포인트의 좌표를 배열에 저장합니다.
2. 거리 계산: 모든 구간의 거리를 계산해 총 이동 거리를 구합니다.
3. 건너뛰기 로직: 두 체크포인트 간의 거리와 기존 구간의 거리를 비교해 최소 이동 거리를 업데이트합니다.

이 코드는 그리디 알고리즘을 활용해 특정 조건(건너뛰는 경우)을 효율적으로 처리했습니다.

---

결과

위 코드를 통해 문제를 해결할 수 있으며, 각 체크포인트에 대한 탐색을 최소화하여 효율적인 풀이를 작성했습니다. 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!