백준 2980 - 도로와 신호등

문제

알고리즘 분류)

• 구현
• 수학
• 시뮬레이션

신호등의 개수:N
도로의 길이:L
각 신호등의 정보:D, R, G
가 주어졌을 때, 상근이가 거리0 부터 거리L까지 가는데 걸리는 시간을 구하면 되고, 상근이는 1초에
거리 1을 이동한다고 한다

풀이

첫번째 생각한 방법)
신호등의 정보를 담은 2차원 배열 signal을 선언해주고
[[R,G], [R,G], [R,G] .... [R,G]] 와 같이 인덱스0에는 R의 시간 , 인덱스1에는 G의 시간을 담아서
1초가 지날때 마다 모든 R과G의 값들을 1씩감소, 증가등을 시켜 상근이가 해당 신호등에 도착하였을때
R과 G의 값에 따라 이동을 결정하려고 하였다
하지만, 모든R과G의 값들을 그때그때 수정한다면 반복문이 사용될 것이므로 시간복잡도 측면에서 비효율적일거라 생각되어 포기.

두번째 생각한 방법)
신호등의 정보를 담은 2차원 배열 signal을 다음과 같이 선언
signal[D] = [0]*R+[1]*G

입력예시)

2 10

3 5 5

5 2 2

3번 신호등 = 빨간불 5초, 초록불 5초
5번 신호등 = 빨간불 2초, 초록불 2초 이므로
배열 signal은

[[],

[],

[],

[0, 0, 0, 0, 0, 1, 1, 1, 1, 1],

[],

[0, 0, 1, 1],

[],

[],

[],

[],

[]]

와 같이 선언되게 된다
만약 상근이가 서있는 곳에 신호등이 없다면 그냥 지나간다
상근이가 서있는 곳에 신호등이 있다면, 현재 시간%상근이가 서있는 곳의 신호등의 길이
로 빨간불인지 초록불인지 판별하여 지나가도록 한다

소스코드

python)

import sys
N,L = map(int,input().split())
signal = [[]]*(L+1) #신호등 배열
sangen = 0
time=0
for _ in range(N):
    D,R,G = map(int,input().split())
    signal[D] = [0]*R+[1]*G
    
while sangen<L: #목표지점에 도달할 때 까지 실행
    if signal[sangen]==[]: #신호등이 없다면
        sangen+=1 #1보 전진
    else:	#신호등이 있다면
        tmp=signal[sangen] #상근이의 위치의 신호등
        if tmp[time%len(tmp)]==1: #신호등이 초록불이면
            sangen+=1 #1보 전진
        else:
            pass
    time+=1 #시간1증가
print(time)