문제
농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.
마라톤 코스는 N (3 ≤ N ≤ 100000) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한개를 몰래 건너뛰려 한다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.
젖소 박승원이 체크포인트 한개를 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?
참고로, 젖소 마라톤 대회는 서울시내 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다. 즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)
입력
첫 번째 줄에 체크포인트의 수 N이 주어진다.
이후 N개의 줄에 정수가 두개씩 주어진다. i번째 줄의 첫 번째 정수는 체크포인트 i의 x좌표, 두 번째 정수는 y좌표이다. (-1000 ≤ x, y ≤ 1000)
체크 포인트의 좌표는 겹칠 수도 있다 - 젖소 박승원은 체크포인트를 건너뛸 때 그 번호의 체크포인트만 건너뛰며, 그 점에 있는 모든 체크포인트를 건너뛰지 않는다.
출력
젖소 박승원이 체크포인트 1개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.
정답코드
#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'
using namespace std;
int main()
{
FASTio;
int n, total = 0,minn=2000000000;
cin >> n;
vector<pair<int,int>> v(n);
vector<int> md(n);
for(int i=0; i<n; i++)
cin >> v[i].first >> v[i].second;
for(int i=1; i<n; i++)
{
md[i]=abs(v[i].first-v[i-1].first)+abs(v[i].second-v[i-1].second);
total += md[i];
}
for(int i=1; i<n-1; i++)
{
int tmp = total;
tmp -= (md[i]+md[i+1]);
minn = min(minn,tmp+abs(v[i+1].first-v[i-1].first)+abs(v[i+1].second-v[i-1].second));
}
cout << minn << endl;
return 0;
}풀이 및 사고과정
일단 데이터 크기와 양을 보니 int 자료형으로 충분할 것 같았고 시간이 문제였다.
일일이 체크포인트 간의 거리를 계산하고 빼면 시간이 불필요하게 많이 소요될 것 같았다.
그래서 일단 전체 거리를 구하고 그때 각 구간의 거리를 구하게 되는데 그 값을 벡터에 저장해놓았다.
그리고 처음부터 끝까지 반복문을 이용해서 한 체크포인트에서 나올 수 있는 거리인 양쪽 두 구간의 길이를 빼주고 양쪽 체크포인트의 거리를 다시 계산하여 값을 구했다. 이렇게 나온 값 중 최저값이 정답이 된다. 그렇게 어렵지않는 문제였다.
