CodeDrive

문제:

개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.

가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오.

입력:

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

출력:

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

풀이 방법:

  문제가 엄청 어려워 보이지만 "또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다. " 이 문장이 함정이라는 것을 알면 어렵지 않게 된다. 실제로 예제 입력에 대해서 계속해서 부딪히게 만들어보았더니 개미가 먼 방향으로 걸어가서 떨어지는 것과 같은 값을 얻는다는 것을 알 수 있었다. (정확한 이유는 모르겠다.)

 따라서 가장 빠른 시간은 각자 개미들이 자신이 위치에서 막대가 짧은 쪽으로 이동하도록 하고, 가장 느린 시간은 개미들이 막대가 긴 쪽으로 이동하도록 한다면 값을 구할 수 있다. 배열에 넣어서 각 값을 구하도록 했더니 시간 초과가 발생해서 각 개미마다 비교해서 최솟값, 최댓값을 구하도록해서 시간을 줄이도록 했다.

문제 링크:

https://www.acmicpc.net/problem/1309