마라톤 1 (feat. 백준, 10655번)

마라톤 1
https://www.acmicpc.net/problem/10655

10655번: 마라톤 1

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, sx, sy, total = 0, t1, t2, t3;
    vector<pair<int, int>> arr;
    cin >> N >> sx >> sy;
    arr.push_back(make_pair(sx, sy));
    for(register int i = 0, x, y; i < N - 1; ++i){
        cin >> x >> y;
        total += abs(x - sx) + abs(y - sy);
        sx = x, sy = y;
        arr.push_back(make_pair(x, y));
    }
    t3 = 0;
    for(register int i = 1; i < N - 1; ++i){
        t1 = abs(arr[i + 1].first - arr[i].first) + abs(arr[i + 1].second - arr[i].second) + abs(arr[i].first - arr[i - 1].first) + abs(arr[i].second - arr[i - 1].second);     // 세 점의 거리 (i + 1과 i의 거리 + i와 i - 1의 거리)
        t2 = abs(arr[i + 1].first - arr[i - 1].first) + abs(arr[i + 1].second - arr[i - 1].second);     // 두 점의 거리 (i + 1과 i - 1의 거리, 즉 i를 건너뛸 경우)
        t3 = max(t3, t1 - t2);
    }
    cout << total - t3;
    return 0;
}
// *&)*@*

 

반응형

 

1. 처음 좌표부터 끝 좌표까지의 전체 길이를 구합니다.
2. 3개의 좌표 위치간 길이를 구합니다. (i + 1와 i 좌표 위치간 거리 + i와 i - 1 좌표 위치간 거리)
3. 3개의 좌표 위치 중 i 좌표 위치를 제외한 길이를 구합니다. (i + 1와 i - 1 좌표 위치간 거리)
4. 2와 3의 차이가 가장 큰 값을 구합니다. (즉, 3번의 i 좌표를 제외했을때와 제외하지 않았을때의 차이가 가장 큰 값)
5. 1번의 전체 길이와 4번의 값의 차이를 출력합니다.