2025 한국정보올림피아드(KOI) 2차 대회 초등부

한국 정보올림피아드(KOI) 기출 문제 풀이과정을 수록합니다.

한국정보올림피아드(KOI) 기출 문제 풀이 모음

1. 장애물 (초1)

제목 링크를 통해 문제를 확인해주세요.

📄 문제 개요

수직선 위 위치 0에서 출발하여 N개의 장애물을 모두 뛰어넘어야 합니다.

• 행동 1: 오른쪽으로 1만큼 걸어간다.
• 행동 2: 오른쪽으로 2만큼 점프한다.
• 장애물 넘기 규칙: 위치 X에 있는 장애물을 넘으려면, 반드시 위치 X-1에서 점프하여 위치 X+1에 도착해야 합니다.

주어진 규칙을 활용해 모든 장애물을 넘기 위한 최소 이동 횟수를 구하고, 만약 넘는 것이 불가능하다면 -1을 출력하는 문제입니다.

위 그림과 같이 한 칸, 혹은 두 칸을 움직여 최종적으로는 최소한의 움직임으로 모든 장애물을 넘어야 합니다.

💡 첫 번째 접근 - 문제 조건대로 하나씩 이동해보기 (Greedy)

가장 확실하고 직관적인 방법은 캐릭터가 직접 이동하는 과정을 코드로 시뮬레이션해 보는 것입니다.

목적지(다음 장애물 앞 칸)까지 가장 적게 이동하려면 자연스럽게 1칸 걷기보다는 2칸 점프를 최대한 많이 활용해야 합니다.

일단 이후는 생각하지 않고, 현재 주어진 위치에서 최대한 앞으로 나가려고 하면 자연스럽게 정답에 도달할 수 있는 문제입니다.

이처럼 지금 당장 눈앞에 보이는 가장 효율적인 선택을 먼저 취하는 방식을 컴퓨터 공학에서는 '그리디(Greedy, 탐욕) 알고리즘'이라고 부릅니다.

• 0 위치: 2칸 앞에 장애물이 있어 2칸을 가지 못하기 때문에 1칸 이동(0 → 1)
• 1 위치: 2칸 앞에 장애물이 없기 때문에 2칸 이동(1 → 3)
• 3 위치: 2칸 앞에 장애물이 있어 2칸을 가지 못하기 때문에 1칸 이동(3 → 4)
• 4 위치: 2칸 앞에 장애물이 없기 때문에 2칸 이동(4 → 6)
• 6 위치: 2칸 앞에 장애물이 없기 때문에 2칸 이동(6 → 8)​
• 8 위치: 2칸 앞에 장애물이 없기 때문에 2칸 이동(8 → 10)
• 10 위치: 2칸 앞에 장애물이 없기 때문에 2칸 이동(10 → 12), 모든 장애물 극복 완료

단, 장애물 두 개가 붙어있는 경우(1칸 앞, 2칸 앞에 모두 장애물이 있는 경우)에는 장애물을 넘지 못한다는 사실을 기억해둡시다.

💻 코드 구현

n = int(input())
arr = list(map(int, input().split()))

last = arr[-1] # 마지막 장애물 위치
x = [0] * (last + 2) # 장애물 위치 기록 / 마지막 장애물을 넘는 것을 고려하여 한 칸 넉넉하게
for i in arr:
    x[i] = 1

s = 0 # 현재 위치
ans = 0
while s < last: # 현 위치가 마지막 장애물보다 앞에 있는 동안
    if x[s+2] == 0: # 2칸 앞에 장애물이 없다면 2칸 전진
        s += 2
    elif x[s+1] == 0: # 1칸 앞에 장애물이 없다면 1칸 전진
        s += 1
    else: # 2칸 앞, 1칸 앞에 모두 장애물이 있으면 불가능
        ans = -1
        break
    ans += 1

print(ans)

이번 문제의 장애물 사이의 거리, 장애물의 개수가 최대 250,000이므로

이렇게 반복문으로 하나하나 시뮬레이션해도 시간초과 없이 안정적으로 100점을 받을 수 있습니다.

💡 두 번째 접근 - 수학적 접근

두 번째 방법은 이동해야할 거리에 따른 횟수를 수학적으로 계산하는 것입니다.

i위치에서 j까지 이동할 때, 두 지점 거리(d)는 j - i 입니다.

이동할 때 최대한 2칸 점프를 많이 활용해야하기 때문에 가능한 만큼 먼저 점프를 활용합니다. (d // 2)

만약 도달하지 못하고 1칸이 남았다면 1칸 걷기를 더해 마무리합니다. (d % 2)

d % 2 값은 0 또는 1이기 때문에 2칸 점프로만 원하는 지점에 도착했더라도 최소 이동 횟수는 d // 2 + d % 2로 계산할 수 있습니다.

위에서 계산한 방식에 따라

[0 → 1(+1)] + 장애물 뛰어넘기(+1) + [3 → 4(+1)] + 장애물 뛰어넘기(+1) + [6 → 10(+2)] + 장애물 뛰어넘기(+1) = 7

이 정답이 되는 것을 확인할 수 있습니다. 장애물을 넘지 못하는 조건은 동일합니다.

💻 코드 구현

n = int(input())
obs = list(map(int, input().split()))

s = 0 # 현재 위치
ans = 0

for i in obs:
    # 장애물이 연속으로 붙은 경우 예외 처리
    if i - 1 < s: 
        print(-1)
        exit()
    
    d = (i - 1) - s # 내 위치부터 다음 장애물 앞 칸까지 남은 거리
    ans += d / 2 + d % 2 # 최소 이동 횟수 누적
    
    # 장애물 뛰어넘기
    ans += 1 
    s = i + 1
    
print(ans)

이번 문제의 경우 장애물 사이의 거리가 25만 칸으로 첫 번째 접근, 두 번째 접근의 시간 차이가 미미한 수준입니다.

하지만 장애물 사이의 거리가 10억 칸으로 늘어난다면 반복문으로 최대 2칸씩 이동하는 방법은 시간이 아주 오래 걸리게 됩니다.

이런 경우 지금처럼 수학적인 접근으로 계산 횟수를 줄여주는 것이 필요합니다.

📊 정답률

2025년도 2차 대회에 진출한 150명 가량의 초등부 학생들 중 130명 가량이 100점,

이외에도 대부분의 학생들이 최소 부분점수는 획득한 문제였습니다.

1차 대회에서 동상을 타고 올라온 학생들인만큼 정답률이 아주 높은 모습입니다.