장애물 timer 1s memory 1024MB

당신은 친구들과 함께 운동장에서 장애물 뛰기 놀이를 하고 있다. 놀이는 수직선 위의 위치 0에서 시작하며, 각 장애물은 왼쪽부터 차례로 X_1<X_2<...<X_N에 놓여 있다. X_1≥1이다.

당신의 목표는 수직선 위에 놓인 N개의 장애물을 모두 뛰어넘는 것이다. 이를 위해 당신은 다음과 같은 두 가지 행동을 할 수 있다:

• 오른쪽으로 1만큼 걸어간다. 즉, 위치 x에서 시작했다면 x+1에 도착한다.

• 오른쪽으로 2만큼 점프한다. 즉, 위치 x에서 시작했다면 x+2에 도착한다.

장애물을 뛰어넘었다는 것은, 장애물을 점프로 넘어갔다는 것을 뜻한다. 다시 말해, 위치 X_i에 있는 장애물을 뛰어넘으려면 반드시 위치 X_i−1에서 오른쪽으로 2만큼 점프해서 위치 X_i+1에 도착해야 한다.

예를 들어, 아래 그림과 같이 수직선 위의 위치 2,5,11에 장애물이 놓여 있다고 가정하자.

다음과 같은 방법들로 장애물을 모두 넘어갈 수 있다. 아래에서 →는 걷기, ⟹는 점프를 의미한다.

• 방법 1: 0→1⟹3→4⟹6→7⟹9→10⟹12 (8회 이동, 장애물 3개 넘음)

• 방법 2: 0→1⟹3→4⟹6⟹8⟹10⟹12 (7회 이동, 장애물 3개 넘음)

하지만, 다음과 같은 방법들은 장애물을 모두 넘어갈 수 없다.

• 방법 3: 0⟹2⟹4⟹6⟹8⟹10⟹12 (6회 이동, 장애물 2개 넘음)

• 방법 4: 0→1⟹3⟹5⟹7⟹9→10⟹12 (7회 이동, 장애물 2개 넘음)

• 방법 5: 0→1⟹3→4→5⟹7 (5회 이동, 장애물 1개 넘음)

각 예시에서, 이동 횟수는 걸어간 횟수와 점프한 횟수의 합이다. 이 예시에서, 방법 2가 최소 이동 횟수로 장애물을 모두 넘어갈 수 있는 최적의 방법이다.

당신은 이동 횟수를 최소화하여 모든 장애물을 넘어가는 최적의 방법을 찾고자 한다. 단, 주어진 두 행동만으로 모든 장애물을 넘어가는 것이 불가능한 경우도 있다.