카테고리 없음코알라_6주차_백준_#11880_파이썬

문제

길이가 L(2 ≤ L ≤ 1,000,000,000)인 막대기 위에 N(1 ≤ N ≤ 100,000)마리의 개미들이 서로 다른 위치에 살고 있다. 개미들은 크기가 매우 작기 때문에 이 문제에서는 개미가 크기가 없는 점이라고 생각하자. 각각의 개미의 위치는 x좌표로 표시되며, 좌표값은 0보다 크고 L보다 작은 값으로 표현된다.

각각의 개미는 왼쪽, 혹은 오른쪽으로 움직이고 있다. 모든 개미들은 똑같은 속도로, 1초에 한 칸씩 움직인다. 개미들이 움직이는 도중에 서로 부딪히는 경우가 생길 수도 있다. 두 마리의 개미가 서로 부딪혔을 때, 두 마리의 개미는 모두 즉시 방향을 바꾸어 다시 움직이게 된다.

개미들이 이동하다가 0인 위치나 L인 위치에 도달하게 되면, 그 개미는 막대기 아래로 떨어지게 된다. 개미들의 초기상태가 주어졌을 때, 가장 마지막에 떨어지는 개미와 그 개미가 떨어지는 시각을 알아내는 프로그램을 작성하시오.

<그림1>

입력

첫째 줄에 두 정수 N, L이 주어진다. 다음 N개의 줄에는 각 개미의 초기 위치가 주어진다. 초기 위치가 양수로 주어지는 경우는 그 값이 그 개미의 위치가 되며, 그 개미는 오른쪽으로 움직이고 있다. 초기 위치가 음수로 주어지는 경우에는 그 절댓값이 그 개미의 위치가 되며, 그 개미는 왼쪽으로 움직이고 있다. 예를 들어 3이 주어지는 경우에는 3인 위치에서 오른쪽으로 움직이고 있고, -7인 경우에는 7인 위치에서 왼쪽으로 움직이고 있다.

출력

첫째 줄에 두 정수 i, t를 출력한다. i는 가장 마지막에 떨어지는 개미의 번호이다. 개미의 번호는 입력에서 주어지는 순서대로 1, 2, …, N이다. t는 가장 마지막에 떨어지는 개미가 바닥에 떨어지는 시간이다. 가장 마지막에 떨어지는 개미가 여러 마리인 경우는 없다고 가정한다.

 

 

<첫번째 코드>

N=int(input())
for i in range(N):
    a,b,c=map(int,input().split())
    d=(a+b)**2+c**2
    print(d)

 

위 그림1과 같이 A에서 윗면 > 옆면을 통해 B로 가는 지점만이 최단거리라 생각하여 위와 같이 코드를 작성하였다.

 

그러나 A에서 윗면 > 옆면을 통해 B까지 가는 것 뿐만 아니라 아래 그림2과 같이

            A에서 옆면 > 밑면  

            A에서 옆면 > 옆면을 통해 B까지 가는 총 3가지 경로가 최단거리의 후보가 되기 때문에

<그림2>

위 3개 중 최솟값이 최단거리이다.

 

<두번째 코드>

N=int(input())
for _ in range(N):
    a,b,c=map(int,input().split())
    d1=(a+b)**2+c**2
    d2=(a+c)**2+b**2
    d3=(b+c)**2+a**2
    print(min(d1,d2,d3))

 

그래서 위와 같이 단순히 3개의 후보들을 다 계산한 뒤, 거기서 최솟값을 출력하는 방식으로 코드를 작성했는데,

이번에는 시간초과가 났다.

 

<세번째 코드>

import sys
input = sys.stdin.readline
N=int(input())
for _ in range(N):
    a,b,c=map(int,input().split())
    tot=a+b+c
    d2=(tot-max(a,b,c))**2+max(a,b,c)**2
    print(d2)

 

그래서 위와같이 연산량을 줄인채로 좀 더 간결하게 코드를 작성하니 이번에는 오류가 나지 않았다.