백준 4307번: 개미 (Python)

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

문제

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

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

입력

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

출력

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

제한

• 1 ≤ n ≤ 100000
• 1 ≤ l ≤ 1000000
• 개미의 위치는 정수
• 0 ≤ 개미의 위치 ≤ l

 

 

 

 

 

 

 

 

 

 

 

 

가장 빠른 시간은 가운데에 가장 가까이 있는 개미가 밖으로 빠지는 데 걸리는 시간이라는 건 간단하게 유추할 수 있다.

가장 늦은 시간은 가장 끝에 있는 개미가 반대쪽 끝까지 가는데 걸리는 시간이라고 하는데, 왜 그럴까? 

나는 1) '가장 가운데 개미가 부딪히는 횟수를 최대한으로 하는 경우'를 따져보고, 2) 3마리일때 해당 명제가 참임을 밝히고(했다.), N마리일때 명제가 참이라고 가정했을 때 N+1마리가 있는 경우를 따져보려고 했으나(수학적 귀납법) 두 방법다 잘 안 됐다. 그래서 웹서핑을 하니,

'부딪히면 방향이 바뀌지만, 생각해보면 개미 개체가 달라졌을 뿐 그대로 가는 거랑 똑같다'라고 생각하면 문제가 간단해진다.

조금 자세히 설명하자면, 개미 A랑 개미 B가 4, 6 위치에 있고 서로를 향해 오는 경우,

1) 부딪히는 경우

	A	B
0초	4	6
1초	5	5
2초	4	6

2) 그냥 지나가는 경우

	A	B
0초	4	6
1초	5	5
2초	6	4

2초의 개미의 위치를 보면, 개미 개체만 달라졌을 뿐 전체적인 위치와 움직임은 1)이나 2)나 똑같다. 즉, 개미는 그냥 서로를 무시하고 지나간다고 생각할 수 있고, 그러면 가장 늦은 시간은 막대의 가장 가장자리에 있는 개미가 반대편 모서리까지 가는데 걸리는 시간이다.

 

 

import sys

 

T = int(sys.stdin.readline())

for i in range(T):

    L, N = map(int, sys.stdin.readline().split())

    ants_location = []

    for i in range(N):

        ants_location.append(int(sys.stdin.readline()))

    ants_location.sort()

    min_time = 0

    max_time = 0

    for ant in ants_location:

        min_time = max(min_time, min(ant, L-ant))

        max_time = max(max_time, ant, L-ant)

    print(min_time, max_time)