[Java/자바 백준 10655] 마라톤 1

풀이

실버 3 문제이지만 체감상 좀 더 어려워서 풀이를 남겨봅니당 !

 

처음 이중 포문으로 브루트포스로 아주 간단히 풀려다가 시간 초과가 났습니다.

 

이후 어떤식으로 풀 수 있을까 생각하다가

모든 체크 포인트를 방문한 값을 distance에 넣어주고

 

체크포인트 한 개를 건너뛰게 되면 줄어드는 거리를 비교해주었습니다.

예를 들어 현재 위치를 i로 예시를 들면

원래라면 i-1, i, i+1값이 있지만

i값을 점프하게되면

i-1, i+1의 위치로 가게 됩니다.

 

이 거리 값을 original과 jump 변수에 각각 넣어주어 최소값을 비교했습니다.

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int[][] checkPoint;
	static int distance ;
	static int min = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		N = Integer.parseInt(br.readLine());
		checkPoint = new int[N][2];
		// 초기값 출발 값 
		for(int i = 0 ; i < N ; i++) {			
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			checkPoint[i][0] = x;
			checkPoint[i][1] = y;
			if(i >= 1) {
				distance += Math.abs(checkPoint[i][0] - checkPoint[i-1][0]) +Math.abs(checkPoint[i][1] - checkPoint[i-1][1]); 
			}
		}
		
		for(int i = 1; i < N-1 ; i++) {
			// jump뛰는 시점 
			int original = Math.abs(checkPoint[i][0]-checkPoint[i-1][0]) 
							+ Math.abs(checkPoint[i][1]-checkPoint[i-1][1])
							+ Math.abs(checkPoint[i][0]-checkPoint[i+1][0]) 
							+ Math.abs(checkPoint[i][1]-checkPoint[i+1][1]);
			int jump = Math.abs(checkPoint[i-1][0] - checkPoint[i+1][0])
						+ Math.abs(checkPoint[i-1][1] - checkPoint[i+1][1]);
			
			min = Math.min(min, distance - original + jump);
		}		
		System.out.println(min);
	}
}