[백준 파이썬] 4307번 개미

[백준 파이썬] 4307번 개미

문제

개미 여러 마리가 길이가 Lcm 인 막대 위에 있다 각 개미는 1초에 1cm씩 이동한다 개미가 막대 마지막 까지 걸어간다면 즉시 떨어지면 두 개미가 만나면 방향을 반대로 바꾸어 걸어가게 된다.

가장 처음 막대 상의 개미의 위치를 알고있지만 어느 방향으로 움직이는지는 알수 없다.

이때 모든 개미가 땅으로 떨어질 때까지 가능한 시간중 가장 빠른 시간과 가장 느린 시간을 구하는 프로그램을 구하시오 

 

입력

첫줄에 테스트 케이스가 주언지다.

각 테스트 케이스의 첫줄은 막대 길이와 개미수n이 주어진다.

n줄에 걸처 개미의 위치가 주어진다.

 

출력

각 테스트 케이스에 대해서 두 숫자를 출력한다.

첫번째 수는 가장빠른 시간 더번째 수는 가장 늦은 시간이다.

풀이

결국 개미는 오른쪽 왼쪽으만 이동가능하다 

오른쪽으로 이동할때 걸리는 시간은 {전체길이 - 현재 개미 위치}

왼쪽으로 이동할때 걸리는 시간은 {현재 위치}  값이다.

자 그렇다면 모든 개미가 가장빠르게 떨어지는 시간은?

각 개미의 오른쪽 ,왼쪽으로 이동할때 떨어지는 시간중 가장 작은값을 모아서 그중 가장 큰 시간이 가장빠르게 모든 개미가 떨어지는 시간이다 왜냐하면 가장 값이 큰 수가 가장 마지막에 떨어진 개미이기에 모든 개미가 떨어지는 가장 빠른 시간을 구할수 있다.

 

이제 모든 개미가 떨어지는 가장 늦은 시간은 각 개미의 오른쪽 왼쪽으로 이동할때 떨어지는 시간중 가장 큰값을 선택하며

그 선택한 값중에서 가장 큰값을 선택하면 모든 개미가 떨어질때까지 필요한 가장 긴 시간이 된다

코드

import sys

input = sys.stdin.readline

test=int(input())
for t in range(test):
    l,n=map(int,input().split())
    array=[]
    for i in range(n):
        a=int(input())
        array.append(a)
    valuemin=[]
    valuemax=[]

    for j in array:
        valuemin.append(min(j,l-j))
        valuemax.append(max(j,l-j))


    print("{} {}".format(max(valuemin),max(valuemax)))

 

시간 초과를 당하기는 했지만 이부분은 처음에 빠른 입출력을 사용하지 않아 시간초과가 생겼다