알고리즘 도전기 - 15
10655 마라톤
문제
농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.
마라톤 코스는 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개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.
예제입력
4
0 0
8 3
11 -1
10 0
예제출력
14
코드
import java.util.*;
public class Main{
public static int[][] distanceList;
public static int i;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
distanceList = new int[N][2];
for(i=0;i<N;i++){
distanceList[i][0]=scanner.nextInt();
distanceList[i][1]=scanner.nextInt();
}
int result = calculDistance(N);
System.out.println(result);
}
public static int calculDistance(int N){
int distance = 0;
int minDistance = -1;
int beforeIdx = -1;
for(i=1;i<N-1;i++){
int beforeCurrentDistance = Math.abs(distanceList[i][0]-distanceList[i-1][0])+Math.abs(distanceList[i][1]-distanceList[i-1][1]);
int passingCurrentDistance = Math.abs(distanceList[i+1][0]-distanceList[i-1][0])+Math.abs(distanceList[i+1][1]-distanceList[i-1][1]);
int currentNextDistance = Math.abs(distanceList[i+1][0]-distanceList[i][0])+Math.abs(distanceList[i+1][1]-distanceList[i][1]);
int subDistance = (beforeCurrentDistance+currentNextDistance)-passingCurrentDistance;
if(minDistance<subDistance){
distance+=passingCurrentDistance;
if(beforeIdx!=-1){
distance-=Math.abs(distanceList[beforeIdx+1][0]-distanceList[beforeIdx-1][0])+Math.abs(distanceList[beforeIdx+1][1]-distanceList[beforeIdx-1][1]);
distance+=Math.abs(distanceList[beforeIdx][0]-distanceList[beforeIdx-1][0])+Math.abs(distanceList[beforeIdx][1]-distanceList[beforeIdx-1][1]);
distance+=Math.abs(distanceList[beforeIdx+1][0]-distanceList[beforeIdx][0])+Math.abs(distanceList[beforeIdx+1][1]-distanceList[beforeIdx][1]);
distance-=beforeCurrentDistance;
beforeIdx=i;
minDistance=subDistance;
}else{
beforeIdx=i;
minDistance=subDistance;
}
}else{
distance+=currentNextDistance;
}
}
return distance;
}
}
Author And Source
이 문제에 관하여(알고리즘 도전기 - 15), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimchiwarrior/알고리즘-도전기-15저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)