[Python] 백준 2980번 문제 풀이 - 도로와 신호등

문제 링크

https://www.acmicpc.net/problem/2980

문제 이해

이 문제는 상근이가 신호등을 거치며 도로의 끝까지 가는데 걸리는 시간을 구하는 문제입니다.

 

우선 첫번째 입력을 예시로 들었을 때

거리 3에 있는 신호등은 1~5초는 빨간불 6~10초는 초록불

거리 5에 있는 신호등은 1~2초는 빨간불 3~4초는 초록불 이렇게 반복이 됩니다.

 

그래서 신호등에 도착했을 때의 현재 시간을 보고 어떤 불인지 계산하여 이동하면 됩니다.

빨간불이 처음 바뀔 때부터 다음 바뀔때까지의 걸리는 시간은 (초록불 시간 + 빨간불 시간)이 걸립니다.

그래서 전체시간 % (초록불 시간 + 빨간불 시간) 연산을 해준다면 사이클 시작 기준(0초)으로 어떤 신호등이 켜져있는지 확인할 수 있습니다.

저 결과가 1~5초라면 빨간불이고, 6~10초라면 초록불이라고 판단할 수 있는 것입니다.

저 결과가 만약에 3초라고 치면 2초를 기다렸다가 6초일 때 출발할 수 있는 것입니다.

아이디어

그래서 나온 아이디어는 다음과 같습니다.

1. 다음 신호등까지 이동한다. (현재 거리와 시간을 더하며)
2. 지금 신호등의 상태를 확인한다.( 전체시간 % (빨간불 시간 + 초록불 시간)
3. 빨간불이면 멈춰서 기다리고(현재 시간에 기다리는 시간 추가), 초록불이면 지나간다.
4. 신호등이 끝났을 때 남은거리만큼 이동한다(현재 거리와 시간을 더하며)

시간복잡도

이 아이디어의 시간복잡도는 O(N) 입니다.

신호등에 도달할때 어떤 불인지 여부를 판단하는 연산만 하면 끝이기 때문입니다.

코드 구현

이 아이디어를 코드로 구현하면 다음과 같습니다.

import sys
input = sys.stdin.readline

n, l = map(int, input().split())

traffic_lights = []

for _ in range(n):
    d,r,g = map(int, input().split())
    traffic_lights.append((d,r,g))

time = distance = 0

for element in traffic_lights:
    (d, r, g) = element
    # 신호등 까지 온 시간과 거리 더해주기
    time += (d - distance)
    distance += (d - distance)
    # 현재 사이클에서 시간이 어느정도 지났는지 확인
    if (time % (r+g)) > r: # 현재 초록불이라면
        continue # 진행
    else: # 빨간불이라면
        time += (r - (time % (r+g))) # 초록불이 될때까지 시간만 추가

# 산호등이 이제 없을 경우 도로 마지막까지 이동
time += (l - distance)

print(time)