백준[ 4307 | Python ] 개미

문제

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

풀이

import sys
input = sys.stdin.readline

t  = int(input().split()[-1])
for _ in range(t):
    l, n = map(int, input().split())
    stick = [0 for _ in range(l+1)]
    ants = [int(input().split()[-1]) for _ in range(n)]
    f_ant = 0
    l_ant = 0
    for i in ants:
        if i > l-i:
            if f_ant < l-i:
                f_ant = l-i
            if l_ant < i:
                l_ant = i
        else:
            if f_ant < i:
                f_ant = i
            if l_ant < l-i:
                l_ant = l-i
    print(f_ant,l_ant)

생각 & 정리

개미의 위치는 막대에서 왼쪽으로부터 얼마나 떨어져 있는지를 나타내고
(막대의 길이 - 개미가 있는 위치)는 개미가 오른쪽으로부터 얼마나 떨어져 있는지 나타낸다.

최소시간은 개미가 가장 빠르게 떨어지기 위해 각자 위치에서 끝이 가까운 쪽으로 향해야한다.
최대시간은 개미가 가장 늦게 떨어지기 위해 각자 위치에서 끝이 먼 족으로 향해야한다.

개미가 만나서 방향을 반대로 바꾸어 걸어가게 되는 경우는 왔던 길을 되돌아 가는 것이기 때문에 결과에 영향을 미치지 않아 무시해야하는 조건이다.