시나브로

길이가 Lcm 인 장대 위를 N마리의 개미가 초당 1cm의 속도로 걷고 있습니다 .개미는 장대의 끝에 도착하면 장대의 및으로 떨어집니다. 또한, 장대 위는 매우 좁아서 교차할 수 없어 두 마리의 개미가 마주치면 반대 방향으로 돌아가야 합니다. 우리는 개미가 장대의 어디에 위치(Xi)하고 잇는지를 알 수 있습니다만, 불행히도 어느 쪽으로 향해 걷고 있는 지는 알 수 없습니다. 모든 개미가 자애로부터 떨어질 때까지 걸리는 최소시간과 최대시간을 각각 구하세요. 이라는 문제가 있었을 때, 재귀 함수로 전체 탐색을 하는 경우를 생각할 수 있다. 의 경우는 2^n으로 계산량이 증가한다. 더 나은 솔류션을 생각해보자. 가장 빠른 시간은 모든 개미가 가까운 장대 끝으로 향하는 것이다. 가장 느린 시간은 반대이면 된다...