문제
직선 모양의 거리에 몇몇 신호등들이 세워져 있다.
신호등들을 통과하여 도로의 한쪽 끝에서 다른 쪽 끝까지 가장 빠른 길로 가는 방법은 단순히 최대한 속력을 내다가 빨간 신호에서 멈추고 다시 출발하는 것이 아니다.
어떤 경우에는 신호등이 초록색으로 바뀔 때까지 약간 느린 속도로 진행하다가 초록색으로 바뀌자마자 원래의 속도를 이용해 빠른 속도로 가는 것이 유리할 수도 있다.
신호등은 Tg 시간동안 초록색, Tr시간동안 빨간색이 되는 것을 반복한다.
도로의 길이와 신호등들의 위치, 상태 등이 주어졌을 때, 도로의 한 쪽 끝에서 다른 쪽 끝까지 이동하는데 드는 최소 시간을 구하자.
매 시각마다 차의 속도는 1만큼 증가할 수도 있고, 1만큼 감소할 수도 있고, 속도가 변하지 않을 수도 있다. 단, 뒤로 가는 것은 불가능하다.
차의 처음 위치는 0 이며, 속도 또한 0 이다.
도로의 다른 쪽 끝에 도착할 때에도 속도가 0 인 상태로 도착해야 한다.
차가 서 있는 위치에 빨간 불이 켜져 있을 때에는 차는 반드시 멈춰야 한다.
신호가 빨간색에서 초록색으로 바뀔 때에는 이동해도 되지만, 초록색에서 빨간색으로 바뀔 때에는 이동할 수 없다.
입력
첫 번째 줄에 도로의 총 길이 L, 신호등의 총 개수 N이 공백으로 구분되어 입력된다. 이후 N개의 줄에 걸쳐 각 신호등에 대한 정보가 입력된다.
첫 번째 숫자는 신호등의 위치를, 이후 두 개의 숫자는 각각 Tg, Tr을 나타낸다.
네 번째에 주어지는 문자는 신호등의 처음 색깔을 나타내며, 다음 숫자는 신호가 마지막으로 바뀐 뒤 흐른 시간을 나타낸다.
[제약조건]
●
●
출력
도로의 반대쪽 끝까지 가는데 필요한 최소 시간을 출력한다.
예제 #1
4 1
1 10 10 R 0
12
예제 #2
1 2
0 1 1 R 0
1 1 1 G 0
2
로그인해야 코드를 작성할 수 있어요.