지능형 교통시스템(Intelligent Transport System)은 이미 우리의 삶에 밀접하게 연결되어 있다. 내비게이션 실시간 교통정보, 고속도로의 하이패스, 정류장의 버스 도착 안내 시스템들이 ITS에 속한다. 여기서 차량과 인프라가 서로 협력하면 차세대 지능형 교통시스템(C-ITS, Cooperative Intelligent Transportation System)이 되는 것이다. 이렇게 차량 주행과 관련된 인프라와 차량 등이 통신하기 시작하면 사고나 정체 상황에서 놀라운 일이 벌어진다.

여기 교통 인프라(신호등)와 실시간 통신을 하는 자율주행차가 가로, 세로 N개의 교차로로 구성된 도로를 지나고 있다. 교차로 간 연결된 선을 도로, 도로의 교차점들을 교차로로 생각하자.

자율주행 차는 처음에 제일 왼쪽 위의 교차로로 아래쪽 방향에서 진입하고 있다. (자동차는 도로 한 칸을 가는 데는 1T가 걸린다.)

각 교차로의 신호등은 다음과 같은 12가지 상태 중 4가지를 가지고 무한히 반복하는 방식으로 운영된다.

예를 들어 한 교차로의 신호 집합이 <3 2 6 10>과 같이 주어진 경우는 아래와 같다.

자율주행 자동차가 멈추지 않고, 시간 T 이내에 갈 수 있는 교차로의 수를 계산하라. 단, 신호가 맞지 않으면 그 교차로에는 갈 수가 없다.

처음에 제일 왼쪽 위의 교차로로 아래쪽 방향에서 진입하고 있으므로, 교차로(1,1)의 신호가 2, 10번 중 하나가 아니면 더 이상 진행을 할 수 없으므로 교차로는 단 하나[교차로(1,1)]로 계산한다.