백준 34200 (C++) 장애물

최초 업로드: 2025-09-24 01:13:28

최근 수정 시간: 2025-09-24 01:13:28

게시자: rlatjwls3333

카테고리: 백준

# [Bronze I] 장애물

[문제 링크](https://www.acmicpc.net/problem/34200)

## 문제 설명

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

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

<ul>
	<li>오른쪽으로 $1$만큼 걸어간다. 즉, 위치 $x$에서 시작했다면 $x + 1$에 도착한다.</li>
	<li>오른쪽으로 $2$만큼 점프한다. 즉, 위치 $x$에서 시작했다면 $x + 2$에 도착한다.</li>
</ul>

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

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

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

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

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

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

## 입력

첫 번째 줄에는 $N$이 주어진다.

두 번째 줄에는 $N$개의 정수 $X_1 , X_2 , \cdots , X_N$이 공백을 사이에 두고 차례대로 주어진다.

## 출력

모든 장애물을 넘어갈 수 없다면, <code>-1</code>을 출력한다.

모든 장애물을 넘어갈 수 있다면, 모든 장애물을 넘기 위해 필요한 최소 이동 횟수를 출력한다.

## 풀이
상자 사이의 거리를 x라 하면 각 상자마다 x/2+1번씩 이동합니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;

int cnt=0, last=0;
 while(n--) {
 int x; cin >> x;
 if(x==last) {
 cout << -1;
 return 0;
 }
 cnt += (x-last)/2+1;
 last = x+1;
 }
 cout << cnt;
}
```