Greedy 백준 알고리즘 자바 4307 ‘개미’ 문제풀이

Problem

개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.

가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오.

Input
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개 줄에는 숫자가 하나씩 주어지며, 이 숫자는 개미의 초기 위치를 나타낸다. 입력으로 주어지는 모든 수는 1,000,000보다 작거나 같으며, 공백으로 구분되어져 있다.

Output
각 테스트 케이스에 대해서, 두 숫자를 출력한다. 첫 번째 숫자는 개미가 모두 땅으로 떨어지는 가능한 시간 중 가장 빠른 시간, 두 번째 숫자는 가장 늦은 시간이다.

Solution

처음에 헉! 했던 문제. 하지만 찬찬히 읽어보면 답이 나온다. 그리디 문제는 뭔가 문제 속에 답이 있고, 그거를 얼마나 빨리 찾냐 못 찾냐 문제인 것 같다. 개미가 어느 방향으로 가는 지 모른다, 반대로 바꾸어 갈 수도 있다. 이런 말들 때문에 혼란이 왔지만, 그리디는 뭔가 엄청난 예외사항을 찾을 필요가 없고 그래서도 안 된다.

우선 정말 간단하게, 가장 빨리 모든 개미가 떨어지는 시간은 모든 개미가 자신과 가장 가까운 막대 끝쪽으로 가면 된다. 즉, 막대기의 절반 L/2를 기준으로 개미의 현 위치가 이보다 크면 막대기 끝쪽으로 가면 되고, 이보다 작으면 막대기의 앞부분으로 가면 된다. 따라서 막대기 끝부분으로 가야하는 개미 중 가장 작은 값이 막대기 끝에서 가장 먼 개미이고 (L - min이 걸리시는 시간), 앞부분으로 가야하는 개미 중 가장 큰 값이 막대기 앞에서 가장 먼 개미이다. (max가 걸린 시간) 이 중 큰 값이 가장 빨리 떨어지는 시간이다. (읭? :)) 가장 오래 걸리는 방법은 막대기 끝으로 가야하는 애가 막대기 앞으로 오거나 막대기 앞으로 가야하는 애가 막대기 끝으로 가는 경우이다. 그래서 정렬을 했다. 이제 연산하면 끝!

Code

import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int tc = scan.nextInt(), l, n, min, max;
		
		for(int i = 0; i < tc; i++) {
			l = scan.nextInt(); n = scan.nextInt();
			int[] points = new int[n];
			min = 1000000; max = 0;
			
			for(int j = 0; j < n; j++) {
				points[j] = scan.nextInt();
				if(points[j] >= l/2)
					min = Math.min(min, points[j]);
				else
					max = Math.max(max, points[j]);
			}
			Arrays.sort(points);
			System.out.println(Math.max(l - min, max) + " " + Math.max(l - points[0], points[n-1]));
		}
	}
}