[백준] 4307 개미

문제 링크: www.acmicpc.net/problem/4307

개미의 방향이 바뀐다는 사항이 훼이크였던 문제였다. 이것때문에 얼마나 고생을 했던지;;

가장 늦은 시간을 구하는 방법이다. 중간에 개미가 부딪쳐서 다시 돌아가는데까지 걸리는 시간과, 그대로 쭉 L까지 가는 시간은 결국 같다.

L이 10이고 개미가 2, 6, 7일때 예시를 들어보겠다.

- 2 개미가  6 개미와 4에서 만난다 . cnt = 2

- 6 개미가 10 방향으로 되돌아가다 7 개미와 4.5에서 마주친다. cnt = 0.5 

- 6 개미가  0 방향으로 가는데까지 걸리는 시간. cnt = 6.5

개미가 가장 늦게 떨어지는 시간은 8초다. 그런데 이는 2 개미가 10까지 쭉 갔을 때 걸리는 시간과 같다. 모든 개미는 1cm/s로 동일하게 움직이므로 중간에 아무리 많은 개미를 만나도 결국 끝점까지 이동하는 거리와 동일하다. 개미의 위치에서 끝 점까지 거리가 긴 값이 가장 시간이  오래 걸리는 답이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_S2_4307_개미 {

	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		int[] input;
		for(int t=0; t<T; t++) {
			StringTokenizer st = new StringTokenizer(in.readLine().trim(), " ");
			int L =  Integer.parseInt(st.nextToken());
			int num = Integer.parseInt(st.nextToken());
			input = new int[num];
			for(int i=0; i < num; i++) {
				input[i] = Integer.parseInt(in.readLine());
			}
			int min = Integer.MIN_VALUE;
			int max = Integer.MIN_VALUE;
			int left = 0, right = 0, tmin = 0, tmax = 0;
			for(int i = 0; i < num; i++) {
				left = input[i];
				right = L - input[i];
				tmin = Math.min(left, right);
				tmax = Math.max(left, right); 
				min = Math.max(min, tmin);
				max = Math.max(max,tmax);
			}
			System.out.printf("%d %d\n", min, max);
		}
				
	}
}

 

 

O(n)으로 풀 수 있다. 나는 개미의 위치를 전부 받아놓고 비교했는데 입력받으면서 계산해도 될 것 같다.

가장 짧은 시간은 0 ~ 개미의 위치, 개미의 위치 ~ L까지를 비교하고 그 중 짧은 것들까리 비교해서 가장 큰 값이다.

가운데를 기준으로 왼쪽에 있는 애들은 0쪽으로 이동하고, 오른쪽에 있는 애들은 L쪽으로 이동하는게 가장 빠르기 때문에 그 중 가장 거리가 먼 애들이 전부 빠져나가면 가장 짧은 시간이 된다.

가장 긴 시간을 구할때는 위의 방법처럼 개미가 0 혹은 L 쪽으로 이동하는 거리가 가장 긴 값이 정답이다.