BOJ - 마라톤1 (10655)

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

10655번: 마라톤 1

 

그리 어렵지 않습니다.

하지만 O(N^2) 알고리즘은 절대 통하지 않습니다.

효율성을 위해서 우선 전체 길이를 구해놓고 시작하면 O(N)으로 줄일 수 있습니다.

 

하나를 건너뛸 때와 건너 뛰지 않을 때의 차를 구해서, 이 중 가장 많이 줄일 수 있는 값을 찾아 

전체 길이에서 빼주면 됩니다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
struct ss {
    int y, x;
};
 
int n, m;
 
vector<ss> v;
 
int main() {
    int ans = 0;
    int cy, cx;
    int total = 0;
 
    cin >> n;
    cin >> cx >> cy;
    v.push_back({ cx, cy });    // 처음에 시작점을 세팅하기 위해 따로 빼줌
 
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({ a,b });
        total += abs(cx - a) + abs(cy - b);    
        cx = a, cy = b;            // 그 다음으로 이동하는 효과를 줌
    }
 
    ans = total;    // 모두 일직선 상에 있다면 길이가 줄어들지 않는다.
    int skip = 0;    // 줄일 수 있는 최댓값을 저장하는 변수
    for (int i = 1; i < n - 1; i++) {    // 시작점과 마지막 점은 건너뛸 수 없으므로
        ss prev = v[i - 1], cur = v[i], next = v[i + 1];
        int dist = abs(prev.x - cur.x) + abs(prev.y - cur.y) + abs(cur.x - next.x) + abs(cur.y - next.y);    // 건너뛰지 않는 경우의 길이 
        int straight = abs(prev.x - next.x) + abs(prev.y - next.y);                                            // 건너뛰는 경우의 길이
 
        skip = max(skip, dist - straight);
    }
 
    cout << total - skip;
}