[백준] 4307번 개미 (자바 풀이)

문제

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

4307번: 개미

 

풀이

이 문제는 애드 훅 문제라고 하는데, 애드 훅이 뭔지 잘 모르겠어서 조사해봤다.

 

일반적으로 경쟁적 프로그래밍(Competitive Programming) 대회, 이른바 알고리즘 대회에서는 종종 애드혹(ad-hoc) 문제가 출제된다. 일반적으로 애드혹 문제라고 하는 것은 해당 문제를 풀기 위해 잘 알려진 정교한(sophisticated) 알고리즘을 적용하지 않고 해결할 수 있는 유형의 문제를 일컫는다. 이러한 유형의 문제는 손으로 직접 해당 문제를 해결하기 위한 (해당 문제만을 위한) 아이디어를 찾아서 문제를 해결할 수 있다. 애드혹 문제들을 굳이 분류하자면 단순히 지시(instruction)를 따르면 되는 구현 유형이나 그리디 유형 알고리즘 혹은 수학 유형으로 분류할 수 있는 경우가 많다.

 

  다시 말해 정형화된 방법론이 아니라, 그 문제를 풀기 위한 창의적인 아이디어를 떠올려야 하는 경우에 애드혹 문제라고 한다.

출처: https://ndb796.tistory.com/474 [안경잡이개발자]

 

한 마디로 푸는 방법이 딱 정해진 게 아니라는 뜻 같다.

 

나도 이 문제를 특정 알고리즘을 사용한 게 아니라 간단하게 해결하였다.

 

먼저, 직관적으로 생각했을 때 개미가 모두 빨리 떨어지는 시간은

max(왼쪽에서 막대 절반까지 길이 중 가장 먼 개미의 거리, 오른쪽에서 막대 절반까지 중 가장 먼 개미의 거리)

이다. 그 이유는 모든 개미가 자신에게서 가장 가까운 곳으로 떨어지기 때문이다.

 

개미가 최대한 천천히 떨어지는 시간은 생각해보면 모든 개미가 자신보다 먼 곳으로 가면 된다.

따라서

max(왼쪽에서 가장 가까운 개미가 오른쪽으로 떨어지는 시간, 오른쪽에서 가장 가까운 개미가 왼쪽으로 떨어지는 시간)

이 정답이다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Baekjoon_4307 {
    static int T,l,n;
    static boolean ant[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        
        while(T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            l = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            ant = new boolean[l+1];
            for(int i=0; i<n; i++) {
                ant[Integer.parseInt(br.readLine())] = true;
            }
            
            int left=l/2,right=l/2;
            while(left>0) {
                if(ant[left]) break;
                left--;
            }
            while(right<l) {
                if(ant[right]) break;
                right++;
            }
            System.out.print(Math.max(left, l-right)+" ");
            left=0; right = l;
            while(left<l) {
                if(ant[left]) break;
                left++;
            }
            while(right>0) {
                if(ant[right]) break;
                right--;
            }
            System.out.println(Math.max(l-left, right));
        }
    }
}