[백준 10655번] 마라톤 1 (C++)

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

10655번: 마라톤 1

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

int n, cx, cy, sum = 0, result = 0, skip = 0;
vector<pair<int, int>> arr;

int main()
{
	fastio;
	cin >> n;
	cin >> cx >> cy;
	arr.push_back({ cx, cy });  //첫 좌표
	
	int nx, ny;
	for (int i = 0; i < n - 1; i++)  //이후 좌표
	{
		cin >> nx >> ny;
		arr.push_back({ nx, ny });
		sum += abs(cx - nx) + abs(cy - ny);  //총 거리 저장
		cx = nx;  //다음 x 좌표를 가리킴
		cy = ny;  //다음 y 좌표를 가리킴
	}

	for (int i = 1; i < n - 1; i++)
	{
		int total_d = 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);        //건너뛰지 않은 거리
		int skip_d = abs(arr[i - 1].first - arr[i + 1].first) + abs(arr[i - 1].second - arr[i + 1].second); //건너뛴 거리
		skip = max(skip, total_d - skip_d);  //차이가 가장 큰 값을 저장
	}
	cout << sum - skip;  //총 거리에서 가장 큰 건너뛴 거리를 뺀 값
}

 

시작점을 위해서 첫 입력값은 따로 빼둔다.

처음에 총 거리를 따로 저장하고, 이후 건너뛴 거리의 최대 값을 따로 계산하여 그 차이를 출력한다.

 

아래 예제 값을 기준으로

4
0 0
8 3
11 -1
10 0

 

총 거리 : 20

 

0 -> 1 -> 2 거리 : 18

0 -> 2 거리 : 12

거리 차이 : 6

 

1 -> 2-> 3 거리 : 9

1 -> 3 거리 : 5

거리 차이 : 4

 

이므로 최소 거리는 20-6으로 14이다.