1. 풀이
난이도에 매몰되지 말것. 실버1이지만 정말 생각하기 어렵다. 쉬운 문제라고 얕보지말고, 어려운 문제라고 겁내지말자
풀어야 할것은 2가지.
㉠가장 마지막에 떨어지는 개미의 시간
㉡가장 마지막에 떨어지는 개미.
개미의 속도가 같고, 만나는 즉시 반대방향으로 간다. 이를 통해 알 수 있는 것 3가지가 있다.
(1) 첫번째, 개미번호만 바뀐 채 같은 개미가 갈길을 그대로 간다고 생각해도 무방하다.
ex)
(좌표) - - 3 - (-5) - - - -
(개미번호) (1) (2)
즉 위와같은 상황에서 (1)개미는 오른쪽으로 가다가 4에서 (2)개미를 만나고, 개미번호만 (2)로 바뀐채 10에서 떨어지고, (2)개미는 왼쪽으로 가다가 4에서 (1)개미를 만나고, 개미번호만 (1)로 바뀐채, 0에서 떨어진다고 생각할 수 있는 것이다.
즉 개미가 언제 떨어지는지는 처음위치에 따라서 정해진다.
=> 이를 통해 ㉠가장 마지막에 떨어지는 개미의 시간을 알 수 있다.
가장 늦게 떨어지는 개미의 시간은 오른쪽으로 향하는 개미중 가장 왼쪽에 있는 개미, 왼쪽으로 향하는 개미중 가장 오른쪽에 있는 개미가 떨어지는 시간 중 더 오래 걸리는 시간이다.
(2) 두번째, 처음에 왼쪽으로 향하는 개미의 수와, 마지막으로 왼쪽으로 떨어지는 개미의 수, 그리고 오른쪽으로 향하는 개미의 수와 오른쪽으로 떨어지는 개미의 수는 각각 같다.
개미는 만나면 각각 방향이 반대로 바뀐다.
ex)
( → ← ) => ( ← → )
즉 각각의 방향(오른쪽, 왼쪽)으로 향하는 개미의 수의 합은 바뀔 수가 없다.
따라서
( → ← ← → → ) 왼쪽으로 향하는 개미2, 오른쪽으로 향하는 개미3 으로 초기 값이 주어지면
떨어질때도 항상 왼쪽으로 2마리, 오른쪽으로 3마리 떨어진다.
(3) 세번째, 처음에 왼쪽으로 향하는 개미가 L개, 오른쪽으로 향하는 개미가 R개이면, 왼쪽 부터 L개는 왼쪽으로 떨어지고, 오른쪽부터 R개는 오른쪽으로 떨어진다.
개미는 만나자마자 방향을 바꾸기 떄문에, 오른쪽에 있던 개미가 왼쪽에 있는 개미를 건너뛸 수 없다. (마찬가지로 왼쪽에 있던 개미가 오른쪽에 있는 개미를 건너뛸 수 없다.)
ex)
( → ← ← → → )
빨간색개미는 왼쪽으로 떨어지면 파란색개미도 무조건 왼쪽으로 떨어지고,
파란색개미가 오른쪽으로 떨어지면, 빨간색개미도 무조건 오른쪽으로 떨어진다.
즉 개미는 다음과 같이 떨어진다.
( ← ← → → → )
=> ii)와 iii)을 통해 ㉡가장 마지막에 떨어지는 개미를 알 수 있다.
ex) ( ← ← → → → )
가장 마지막에 떨어지는 개미는 왼쪽으로 떨어지는 개미 중 가장 늦게 떨어지는 파란색, 오른쪽으로 떨어지는 개미중 가장 늦게 떨어지는 빨간색 둘 중 하나이다. 이때 각각의 시간은 ㉠가장 마지막에 떨어지는 개미의 시간 에서 구했던 것을 이용하면 된다.
2. 소스코드
N,total=map(int,input().split())
oriL=[]
for i in range(N):
oriL.append(int(input()))
L=sorted(oriL,key=abs)
# 가장왼쪽개미가 떨어지는 시간
leftTime=0
for i in range(N):
if L[i]>0:
leftTime=total-L[i]
leftIndex=i
break
# 가장 오른쪽 개미가 떨어지는 시간
rightTime=0
for i in range(N-1,-1,-1):
if L[i]<0:
rightTime=L[i]*(-1)
rightIndex=i
break
toRight=0
toLeft=0
for i in range(N):
if L[i]:
if L[i]>0:
toRight+=1
else:
toLeft+=1
#왼쪽게 가장늦게 떨어질때
if leftTime>rightTime:
print(oriL.index(L[toLeft])+1,leftTime)
#오른쪽게 가장 늦게 떨어질때
else:
print(oriL.index(L[toLeft-1])+1,rightTime)