BOJ 2980 - 도로와 신호등

문제

BOJ 2980 - 도로와 신호등

길이 L인 도로에 N개의 신호등이 있다. 각 신호등은 빨간불 R초, 초록불 G초를 반복하며 시간 0에서 빨간불로 시작한다. 사람은 속도 1로 이동하며, 빨간불이면 초록불이 될 때까지 대기한다. 도로 끝까지 도달하는 시간을 구하라.

입력

신호등 수 N과 도로 길이 L, 이후 N줄에 각 신호등의 위치 D, 빨간불 시간 R, 초록불 시간 G가 주어진다.

출력

도로 끝에 도착하는 시간을 출력한다.

예제

풀이

신호등을 순서대로 방문하며, 도착 시점의 신호 상태를 계산하여 대기 시간을 누적한다.

1. 현재 위치에서 신호등까지의 거리를 이동 시간에 더한다
2. 도착 시점을 신호 주기 (R + G)로 나눈 나머지가 R 이하이면 빨간불이다
3. 빨간불이면 R - 나머지만큼 대기 시간을 추가한다
4. 모든 신호등을 처리한 후, 마지막 신호등에서 도로 끝까지의 거리를 더한다

핵심 아이디어: 신호등의 주기는 R + G이고 시간 0에서 빨간불이 시작하므로, 도착 시간을 주기로 나눈 나머지로 현재 신호 상태를 판별할 수 있다.

코드

import sys
 
input = sys.stdin.readline
 
N, L = map(int, input().split())
pos = 0
answer = 0
 
for _ in range(N):
    d, r, g = map(int, input().split())
 
    answer += d - pos
    pos = d
    if answer % (r + g) <= r:
        answer += r - (answer % (r + g))
 
answer += L - pos
print(answer)

복잡도

• 시간: O(N) — 신호등 수만큼 순회
• 공간: O(1) — 상수 공간