루미 알고리즘

#1115실버장애물장애물

KOI 2025 2차코딩초등부 1번출제 오주원이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

장애물

원제: 장애물

문제

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

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

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

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

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

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

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

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

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

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

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

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

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

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

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

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

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

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

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

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

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤250 0001 \le N \le 250\,000
  • 1≤X1<X2<...<XN≤250 0001 \le X_1 < X_2 < ... < X_N \le 250\,000

부분문제

  1. (7점) N=1,X1≤5N = 1, X_1 \le 5
  2. (12점) N=1,X1≤5 000N = 1, X_1 \le 5\,000
  3. (23점) N≤5 000N \le 5\,000, 1≤i≤N1 \le i \le N인 모든 ii에 대하여 Xi≤5 000X_i \le 5\,000
  4. (58점) 추가 제약 조건 없음.

입력 형식

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

두 번째 줄에는 NN개의 정수 X1,X2,⋯ ,XNX_1, X_2, \cdots, X_N이 공백을 사이에 두고 차례대로 주어진다.

출력 형식

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

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

예제

예제 1

입력
3
2 5 11
출력
7

예제 2

입력
3
7 20 25
출력
14

예제 3

입력
4
1 4 5 8
출력
-1

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2025년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.