알고리즘/문제 풀이
[Java/자바 백준 10655] 마라톤 1
광규니
2022. 2. 22. 00:27
반응형
풀이
실버 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);
}
}
반응형