[백준 4307번] 개미 풀이

4307번: 개미

 

T개의 테스트 케이스에 대하여 막대의 길이 L과 개미의 수 N이 주어진다. 개미는 모두 1m/s로 이동하고 충돌시 반대 방향으로 움직인다.

 

'개미가 서로 충돌할 때 반대 방향으로 움직인다'는 조건은 고려하지 않아도 된다. 그 이유를 살펴보면,

 

서로 반대방향으로 움직이고 있는 두 개미

 

1차원 상의 좌표에 반대방향으로 움직이는 두 개미가 있다. 두 개미가 충돌하면 각 개미의 진향 방향이 반대가 되므로,  다음과 같은 과정을 거친다.

 

 

충돌 직후의 두 개미

진행 방향이 바뀐 두 개미

 

문제에서 모든 개미를 똑같이 취급하고 있으므로(개미에게 번호를 부여한다던가... 그런 건 없다) 두 개미의 색깔(identity)를 바꿔 취급해도 상관이 없다. 개미의 충돌전 상태와 충돌 후 색깔이 바뀐 상태를 비교해보자.  충돌 결과는 각 개미가 진행 방향 그대로 움직인 것과 다름이 없다.

 

두 개미의 색깔을 바꿨을 때

 

개미가 침대로 모두 떨어지는 최소 시간은, 모든 개미가 현재 위치로 부터 가까운 막대의 끝으로 움직일 때 필요한 시간들 중 최대 시간을 구하면 된다. 반대로, 침대로 모두 떨어지는 최대 시간은, 모든 개미가 현재 위치로 부터 먼 막대의 끝으로 움직일 때 필요한 시간들 중 최대 시간을 구하면 된다.

 

현재 개미의 위치에서 가까운 끝과 먼 끝까지의 시간은 다음과 같이 구할 수 있다.

 

//현재의 위치 pos에서 막대의 가까운 끝
int sht = min(pos, L-pos);

//현재의 위치 pos에서 막대의 먼 끝
int lng = max(pos, L-pos);

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
using namespace std;

int main() {

    int T;
    scanf("%d", &T);

    for (int t=0; t<T; t++) {
        
        int L, N;
        scanf("%d %d", &L, &N);

        int minTime = 0, maxTime = 0;
        for (int n=0; n<N; n++) {
            int pos;
            scanf("%d", &pos);
            
            int sht = min(pos, L-pos);
            int lng = max(pos, L-pos);
            minTime = max(minTime, sht);
            maxTime = max(maxTime, lng);
        }
        
        printf("%d %d\n", minTime, maxTime);
    }
    return 0;
}