[프로그래밍 콘테스트 챌린지] Ants(POJ No.1852)

길이가 Lcm 인 장대 위를 N마리의 개미가 초당 1cm의 속도로 걷고 있습니다 .개미는 장대의 끝에 도착하면 장대의 및으로 떨어집니다. 또한, 장대 위는 매우 좁아서 교차할 수 없어 두 마리의 개미가 마주치면 반대 방향으로 돌아가야 합니다. 우리는 개미가 장대의 어디에 위치(Xi)하고 잇는지를 알 수 있습니다만, 불행히도 어느 쪽으로 향해 걷고 있는 지는 알 수 없습니다. 모든 개미가 자애로부터 떨어질 때까지 걸리는 최소시간과 최대시간을 각각 구하세요.

이라는 문제가 있었을 때, 재귀 함수로 전체 탐색을 하는 경우를 생각할 수 있다. 의 경우는 2^n으로 계산량이 증가한다. 

더 나은 솔류션을 생각해보자.

가장 빠른 시간은 모든 개미가 가까운 장대 끝으로 향하는 것이다. 가장 느린 시간은 반대이면 된다. 이럴 경우, 두 마리의 개미가 마주친다면 어떻게 되는 것인가? 인다. 해답은 간단한다. 마주칠 때, 방향을 바꾼다고 생각하지 말고 통과한다고 생각하면 된다.

 

이렇게 되면 O(n)의 시간 복잡도를 가진다.