찰떡개발자 코딩

그리디 알고리즘 문제 2번째 - 백준 개미

문제 : https://www.acmicpc.net/problem/4307

풀이 :

괜히 복잡하게 생각했다가 낭패봤던 문제....

간단하게 풀이를 설명하자면.

개미가 만나서 반대로 돌고 하는 부분을 생략하고 생각하면된다.  함정....!

결국

최소 시간= 개미들이 다떨어지는 시간 = 끝에서 가장 멀리있는 개미의 위치 = 1개미 마다 양끝에서의 거리를 재서 가장 짧은 거리를 기준으로 temp를 만든다. => 그 temp 값이 가장 작은 값

최대 시간= 1개미 마다 양끝에서의 거리를 재서 가장 긴 길이

함정만 피하면 아주 심플한 코드가 된다...

그럼 왜 함정일까? 

경우의 수를 종이에 그려봤다.... ㅠ 멍청이

개미가 만나서 방향을 바꿔도 현재 위치 값을 기준으로 계산하는것보다 작거나 같다는것...!

public static void main(String[] args) throws IOException {
    	Scanner scan = new Scanner(System.in);
		int tc = scan.nextInt(), l, n;
		for(int i = 0; i < tc; i++) {
			l = scan.nextInt();
			n = scan.nextInt();

			int min = 0;
			int max = 0;
			for (int j = 0; j < n; j++) {
				int ant = scan.nextInt();
				//최소 시간 : 왼쪽으로 떨어지는 시간 , 오른쪽으로 떨어지는시간 비교하여 작은값 중 큰값이 전체의 최소시간
				int temp = Math.min(ant, l-ant);
				min = Math.max(min, temp);
				//최대 시간 : 양끝에서의 거리중 큰 값
				max = Math.max(ant,max);
				max = Math.max(l-ant,max);
			}
			System.out.println(min +" "+ max);
		}
    }

아주 간단한 코드로 끝났다....

화이팅!