[C++][백준] 4307 개미

이번 문제는 간단한 구현 문제이다.
문제는 어려워 보이지만 약간 생각을 다르게 한다면 쉬운 문제가 된다.

문제

개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.
가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

이런식으로 개미들이 돌아다닌다고 가정을 했을 때, 개미들이 부딪힌다고 해서 딱히 전체적인 상황은 변화하지 않는다.
다시말해 개미들은 서로 구분되지 않기 때문에 가운데 개미가 충돌해서 방향을 바꾸는 상황이 서로 관통해서 지나가는 상황과 결과가 바뀌지 않는다.

 

코드를 살펴보자

#include <bits/stdc++.h>
int l,n;
int x;
int N;
int Max, Min;
using namespace std;
bool neworder(int a, int b) {
    return abs(l/2-a) < abs(l/2-b);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;

    for(int j=0; j<N; j++) {
        cin >> l >> n;
        vector<int> arr;
        arr.clear();
        for (int i = 0; i < n; i++) {
            cin >> x;
            arr.push_back(x);
        }
        sort(arr.begin(), arr.end());
        if ((l - arr.front()) > arr.back()) //Max 구하기
            Max = l - arr.front();
        else
            Max = arr.back();
        sort(arr.begin(),arr.end(), neworder);
        if(l-arr[0]<arr[0])
            Min = l-arr[0];
        else
            Min = arr[0];
        cout << Min <<' '<< Max << '\n';
        }
        return 0;
    }

• 가장 빠른 시간과 느린 시간을 구해야 한다.
• 가장 빠른 시간은 막대의 가운데와 가장 가깝게 있는 개미가 더 짧은 쪽으로 떨어질 때까지 걸리는 시간이고
• 가장 느린 시간은 가운데와 가장 멀리 떨어진 개미가 반대쪽으로 떨어질 때까지 걸리는 시간이다.