백준 [자바 java] 10655번 : 마라톤

https://www.acmicpc.net/problem/10655

이 문제는 딱 봤을 때 브루트포스 문제임을 알 수 있었다. 

그런데 단순히 처음부터 끝까지 매번 계산하는 것 보다 누적합을 쓰는 것이 더욱 효율적이라는 생각이 들어 그렇게 풀었다.

 

for(int i = 0;i<n;i++){
  st = new StringTokenizer(br.readLine());
  arr[i][0] = Integer.parseInt(st.nextToken());
  arr[i][1] = Integer.parseInt(st.nextToken());
}

먼저 각 좌표의 값을 입력받는다.

 

for(int i = 1;i<n;i++){
  int now = Math.abs(arr[i][0] - arr[i-1][0]) + Math.abs(arr[i][1] - arr[i-1][1]);
  nu[i] = nu[i-1] + now;
}

그 다음 누적합 배열을 생성한다. 

now는 현재 노드와 이전 노드의 거리를 뜻한다. 거리는 절댓값을 사용해야하니까 Math 라이브러리의 abs를 사용하였다.

 

이 값을 누적합 배열의 이전 값과 더한다.

 

int ans = Integer.MAX_VALUE;

for(int i = 1;i<n-1;i++){
  int dis = nu[i-1] + (nu[n-1] - nu[i+1]) + Math.abs(arr[i-1][0] - arr[i+1][0]) + Math.abs(arr[i-1][1] - arr[i+1][1]);
  if(dis < ans) ans = dis;
}

ans는 가장 작은 값이 되어야하므로, 초기값은 가장 큰 값으로 잡는다.

그 다음 각 노드를 건너 뛸 때마다의 거리를 측정한다.

만약, i번째 노드를 건너뛴다면, 누적합의 i-1 노드 값(해당 노드 전까지 이동하는데 걸리는 거리) + 누적합 가장 끝 값에서 누적합 i+1번째 노드 값을 뺀 값( 해당 노드 후에서 도착지점까지의 거리)를 한 후

i-1노드에서 i+1 노드까지의 거리를 구해 더한다.

 

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


public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    StringTokenizer st;

    int[][] arr = new int[n][2];
    int[] nu = new int[n];

    for(int i = 0;i<n;i++){
      st = new StringTokenizer(br.readLine());
      arr[i][0] = Integer.parseInt(st.nextToken());
      arr[i][1] = Integer.parseInt(st.nextToken());
    }

    for(int i = 1;i<n;i++){
      int now = Math.abs(arr[i][0] - arr[i-1][0]) + Math.abs(arr[i][1] - arr[i-1][1]);
      nu[i] = nu[i-1] + now;
    }

    int ans = Integer.MAX_VALUE;

    for(int i = 1;i<n-1;i++){
      int dis = nu[i-1] + (nu[n-1] - nu[i+1]) + Math.abs(arr[i-1][0] - arr[i+1][0]) + Math.abs(arr[i-1][1] - arr[i+1][1]);
      if(dis < ans) ans = dis;
    }

    System.out.println(ans);

  }
}