[알고리즘] 백준 13411 파이썬 - 하늘에서 정의가 빗발친다!

 

13411번: 하늘에서 정의가 빗발친다!

문제

오버워치에 빠진지도 어언 6개월. 50점에서 시작한 경쟁전 점수는 어느새 35점까지 내려와 버렸다. 알고리즘을 공부하느라 게임 실력이 떨어졌다고 생각한 규현이는 오버워치 경쟁전 점수를 올리기 위해 새로운 캐릭터 파라를 선택하여 연습을 시작하였다. 포화 개시! 처음 사격을 시작한 규현이의 파라는 형편없는 명중률을 보여주었지만, 곧이어 모든 미사일이 적의 로봇을 명중시키는 놀라운 결과를 얻어내었다. 파라를 계속 연습하던 규현이는 파라가 미사일을 쏘는 순간, 알고리즘 능력이 발휘되어 그 장면이 머릿속에서 좌표평면으로 그려졌다. 

규현이의 파라는 (0,0) 의 위치에 있으며, 궁극기를 사용할 시 미사일을 적의 모든 로봇에게 동시에 직선으로 발사하여 맞춘다. 미사일의 날아가는 속도가 미사일마다 모두 달라 더 멀리 있는 적을 가까이 있는 적보다 더 빨리 맞출 수도 있게 된다. 알고리즘의 늪에서 빠져나올 수 없었던 걸까? 규현이는 적이 미사일에 격추되는 순서를 구하는 프로그램을 만들려고 한다. 규현이를 도와 프로그램을 작성하시오.

 

 

문제풀이

import sys
input = sys.stdin.readline
n=int(input())
tmp=[]
#01
for i in range(1,n+1):
    x,y,v=map(int,input().split())
    d = (x**2+y**2)**0.5
    tmp.append((d/v,i))
#02
tmp.sort(key=lambda x:(x[0],x[1]))
for i in range(n):
    print(tmp[i][1])

- #01 : for문을 통해 i를 1~n까지 실행한다.

           x,y,v를 입력받아 d 즉 거리를 피타고라스의 정리를 이용하여 x,y로 구하고,

           tmp에는 거리/속도를 한 값과 i를 추가해준다.

- #02 : tmp를 (거리/속도)로 오름차순 정렬 후 값이 같다면 i로 오름차순 정렬한다.

           즉 거리/속도는 시간을 의미한다. 다시말해, 미사일이 도착하는데 걸린 시간이라는 의미이다.

           정렬된 tmp 중에 2번째 값, 즉 로봇의 순서를 출력해준다.