[백준] 2136 개미 / 자바(Java)

• 문제

• 해설

• 주의점

• 코드

문제

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

2136번: 개미

 

---

해설

직선상에 있는 여러 개미들 중에 마지막으로 떨어지는 개미의 순번과 떨어지는 시간을 구하는 문제입니다.

 

처음에는 일일히 구현으로 해결해 보려했으나 시간초과로 실패해 찾아본 결과 나온 풀이는 

'떨어지는 시간' 과 '마지막으로 떨어지는 개미'를 나누어 구하는 것 입니다.

문제의 작동방식을 보고 분석을 통해 이를 위한 근거를 알아내었습니다.

 

1. 떨어지는 시간 - 개미의 번호를 지우고 본다면 각 개미는 만나더라도 각자 갈길을 간다.

 

예시를 2가지를 들어보겠습니다.

1) 개미 2마리가 딱 맞아 떨어지는 경우

(좌표) - - 3 - (-5) - - - -
(개미번호) (1) (2)

이라 한다면 

(좌표) - - - 3,(-5) - - - - -  +1초
(좌표) - - 3 - (-5) - - - -  +2초
(좌표) - 3 - - - (-5)  - - -  +3초

이 됩니다. 하지만 서로 튕겨나가지 않고 지나갔다 하더라도

(좌표) - - (-5) - 3 - - - -  +2초
(좌표) - (-5) - - - 3 - - -  +3초

으로 개미 번호를 때고 본다면 결국 같은 위치에서 같은 방향으로 움직이는 2마리의 개미가 됩니다.

 

2) 개미 2마리가 교차하는 경우

(좌표) - - - 4 (-5) - - - -
(개미번호) (1) (2)

이라 한다면 

(좌표) - - 3 - - (-5) - - -  +1초
(좌표) - 3 - - - - (-5) - -  +2초

이 됩니다. 하지만 서로 교차하지 않고 지나갔다 하더라도

(좌표) - - (-5) - - 3 - - -  +2초
(좌표) - (-5) - - - - 3 - -  +3초

으로 개미 번호를 때고 본다면 결국 같은 위치에서 같은 방향으로 움직이는 2마리의 개미가 됩니다.

 

일직선에서 개미가 만날 2가지 가능성 모두 각 개미가 만나도 각자 갈길 가는 경우와 같다는 것이 확인됩니다.

이를 통해 특정 위치(point)에 개미가 있어서 왼쪽으로 간다면 |point|초 후에 어떤 개미가 떨어지고, 오른쪽으로 간다면 L-point초 후에 어느 개미가 떨어지게 될 것임을 알았습니다.

 

문제에서는 가장 늦게 떨어지는 개미를 구해야 하므로 왼쪽으로 가는 가장 큰 경우(minusMax)와 오른쪽으로 가는 가장 큰 경우(plusMax) 두가지를 구해두겠습니다. 

 

2. 마지막으로 떨어지는 개미 - 각 방향으로 떨어지는 개미의 수는 시작할때 각 방향을 보는 개미의 수와 같다
                                               - 각 방향에 서있는 개미들은 결국 그쪽 방향으로 떨어진다.

 

1) 각 방향으로 떨어지는 개미의 수는 시작할때 각 방향을 보는 개미의 수와 같다

개미들은 만나면 서로 반대방향으로 이동합니다.

(→ ←)  ==> (← →)

이는 결국 왼쪽으로 가는 개미와 오른쪽으로 가는 개미의 수는 변하지 않습니다.

좀 더 복잡한 예시로

( → ← ← → → )  
( ← → ← → → ) 
( ← ← → → → ) 

처음 왼쪽을 보던 개미 2마리, 오른쪽을 보던 개미 3마리에서 

최종적으로 왼쪽으로 2마리, 오른쪽으로 3마리가 떨어지는 것을 볼 수 있습니다.

 

2) 각 방향에 서있는 개미들은 결국 그쪽 방향으로 떨어진다.

예시의 마지막 상태를 보면 왼쪽으로 떨어지는 개미들은 왼쪽으로, 오른쪽으로 떨어지는 개미들은 오른쪽으로 결국 같은 쪽으로 떨어지는 순서대로 개미들이 뭉쳐있음을 알 수 있습니다.

( ← ← → → → ) 

 

2)와 3)을 근거로 왼쪽으로 떨어지는 마지막 개미와 오른쪽으로 떨어지는 마지막 개미의 순번을 알 수 있습니다.

( ← ← → → → ) 

처음에 왼쪽으로 2마리, 오른쪽으로 3마리가 이동하고 있었기 때문에

결국 왼쪽에서 2번째 개미가 왼쪽으로 떨어지는 개미들 중 가장 마지막에 떨어지고,

오른쪽에서 3번째 개미가 오른쪽으로 떨어지는 개미들 중 가장 마지막에 떨어집니다.

 

 

 

2가지 조건( '떨어지는 시간' 과 '마지막으로 떨어지는 개미')를 통해

왼쪽으로 마지막에 떨어지는 개미의 순번과 시간, 오른쪽으로 마지막에 떨어지는 개미의 순번과 시간을 모두 구했습니다

최종적으로 마지막에 떨어지는 개미를 둘을 비교해서 얻어낼 수 있습니다.

 

주의점

• 개미의 움직임을 모두 계산하려 하지말고 '어느 개미'가 '언제 떨어지는가'를 나누어 구한다.
• 애드혹(ad-hoc)인지라 직선상의 부딪히면 튕기는 경우에 사용가능하다는 거만 알아두면 다음에 사용 가능하다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class pair implements Comparable<pair> {
        int i;
        int abs;
        pair(int i, int abs){
            this.i = i;
            this.abs = abs;
        }

        @Override
        public int compareTo(pair o) {
            return this.abs-o.abs;
        }
    }
    static int L=0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        int minuscount = 0;
        int plusMax = 0;
        int minusMax = 0;
        int point[] = new int[N+1];
        pair arr[] = new pair[N+1];
        for(int i=1;i<=N;i++){
            int input = Integer.parseInt(br.readLine());
            point[i] = input;
        }

        for(int i=1;i<=N;i++){
            if(point[i]>=0){
                plusMax = Math.max(plusMax,L-point[i]);
            }else{
                minuscount++;
                minusMax = Math.max(minusMax,Math.abs(point[i]));
            }
            arr[i-1] = new pair(i,Math.abs(point[i]));
        }
        Arrays.sort(arr,0,N);
        if(plusMax>minusMax){
            System.out.println(arr[minuscount].i+" "+plusMax);
        }else {
            System.out.println(arr[minuscount-1].i+" "+minusMax);
        }
    }
}