BOJ 2136 개미
https://www.acmicpc.net/problem/2136
시간 2초, 메모리 128MB
input :
- N L(2 ≤ L ≤ 1,000,000,000)(1 ≤ N ≤ 100,000)
- pos (0 < pos < L)
output :
- i t
- i는 가장 마지막에 떨어지는 개미의 번호
- t는 가장 마지막에 떨어지는 개미가 바닥에 떨어지는 시간
조건 :
-
개미의 번호는 입력에서 주어지는 순서대로 1, 2, …, N이다.
-
각각의 개미는 왼쪽, 혹은 오른쪽으로 움직이고 있다
-
모든 개미들은 똑같은 속도로, 1초에 한 칸씩 움직인다.
-
두 마리의 개미가 서로 부딪혔을 때, 두 마리의 개미는 모두 즉시 방향을 바꾸어 다시 움직이게 된다.
-
개미들이 이동하다가 0인 위치나 L인 위치에 도달하게 되면, 그 개미는 막대기 아래로 떨어지게 된다.
연관 문제
위의 문제와 동일한 문제이다.
그러나 위치가 증가하는 순서가 아니기 때문에 이에 대한 정렬이 수행되어야 함.
출력 조건 : "가장 마지막에 떨어지는 개미가 여러 마리인 경우는 없다고 가정한다."이로 인해 2마리가 동시에 떨어지는 경우는 없다.
import sys
n, l = map(int, sys.stdin.readline().split())
ids, left, right = [], [], []
for i in range(n):
pos = int(sys.stdin.readline())
ids.append((abs(pos), i + 1))
if pos > 0:
right.append(l - pos)
else:
left.append(-pos)
ids.sort()
left.sort()
right.sort(reverse=True)
move = left + right
ans = [(move[i], ids[i][1]) for i in range(n)]
ans.sort()
print(ans[-1][1], ans[-1][0])
Author And Source
이 문제에 관하여(BOJ 2136 개미), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-2136-개미저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)