직선 모양의 거리에 몇몇 신호등들이 세워져 있다.

신호등들을 통과하여 도로의 한쪽 끝에서 다른 쪽 끝까지 가장 빠른 길로 가는 방법은 단순히 최대한 속력을 내다가 빨간 신호에서 멈추고 다시 출발하는 것이 아니다.

어떤 경우에는 신호등이 초록색으로 바뀔 때까지 약간 느린 속도로 진행하다가 초록색으로 바뀌자마자 원래의 속도를 이용해 빠른 속도로 가는 것이 유리할 수도 있다.

신호등은 Tg 시간동안 초록색, Tr시간동안 빨간색이 되는 것을 반복한다.

도로의 길이와 신호등들의 위치, 상태 등이 주어졌을 때, 도로의 한 쪽 끝에서 다른 쪽 끝까지 이동하는데 드는 최소 시간을 구하자.

매 시각마다 차의 속도는 1만큼 증가할 수도 있고, 1만큼 감소할 수도 있고, 속도가 변하지 않을 수도 있다. 단, 뒤로 가는 것은 불가능하다.

차의 처음 위치는 0 이며, 속도 또한 0 이다.

도로의 다른 쪽 끝에 도착할 때에도 속도가 0 인 상태로 도착해야 한다.

차가 서 있는 위치에 빨간 불이 켜져 있을 때에는 차는 반드시 멈춰야 한다.

신호가 빨간색에서 초록색으로 바뀔 때에는 이동해도 되지만, 초록색에서 빨간색으로 바뀔 때에는 이동할 수 없다.

신호등 timer 1s memory 256MB

신호등 1s 256MB