[POJ] 1852.cpp : Ants

poj.org/problem?id=1852

1852 -- Ants

---

창의적인 사고력이 뒷받침되어야 하는 문제이다.

 

먼저 생각할 수 있는 해결책은, 모든 개미가 향하는 방향을 전부 검사하는 것이다.

한 마리에 대해 좌/우 2가지가 있어 2의 n 승이 되는데, 단순히 생각해봐도 실행시간이 급격하게 증가할 것으로 예상된다.

지수시간 알고리즘에서는 큰 입력을 처리하는 것은 불가능하다.

 

보다 효율적인 방법은 없을까?

 

우선 최소시간의 경우는 모든 개미가 장대 끝의 가까운 곳을 향하고 있는 것이다.

이 경우에는, 개미가 서로 마주치는 일이 없으며 이보다 짧은 시간 안에 도달하는 방법도 없다.

 

그렇다면 최대시간의 경우는 어떻게 될까?

두 마리의 개미가 마주쳤을 경우에 두 개미는 다시 반대 방향으로 돈다고 한다.

하지만 이것은 돌아서지 않고 서로 지나쳐 간다고 생각해도 문제가 되지 않는다.

개미 두마리의 구분을 없애면, 두 개미가 되돌아가는 것이 결국에는 서로 뚫고 가는 것과 같아진다.

이렇게 생각하면 개미가 서로 부딪히는 일을 고려하지 않아도 되기 때문에, 장대 끝까지의 거리의 최댓값을 구하면 되는 것이다.

 

이 경우의 시간 복잡도는 각자의 장대 끝까지의 최댓값을 한번씩만 구하면 되기 때문에 O(n) 이 되고, 1,000,000 개의 입력값들은 시간제한 안에 충분히 해결 가능해진다.

---

#include <iostream>
#include <algorithm>
using namespace std;

int t;
int len, n;
int x[1000001];

int main(void)
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> t;
    while(t--)
    {
        int _min = 0, _max = 0;
        cin >> len >> n;
        for(int i = 0 ; i < n ; i++)
        {
            cin >> x[i];
        }
        for(int i = 0 ; i < n ; i++)
        {
            _min = max(_min, min(x[i], len - x[i]));
            _max = max(_max, max(x[i], len - x[i]));
        }

        cout << _min << " " << _max << '\n';
        for(int i = 0 ; i < n ; i++)
        {
            x[i] = 0;
        }
    }
}