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차 대회에서 동상을 타고 올라온 학생들인만큼 정답률이 아주 높은 모습입니다.

2. 거울 (초2/중1)

📄 문제 개요

수직선 위의 위치 s에서 출발하는 캐릭터가 있습니다. 그리고 수직선 위에는 N개의 거울이 놓여 있습니다.

• 이동 규칙: 위치 a에 있는 캐릭터가 위치 b에 있는 거울을 사용하면, 거울을 기준으로 점대칭인 지점인 2b - a 위치로 이동하게 됩니다.
• 조건: N개의 거울을 원하는 순서대로 정확히 한 번씩 모두 사용해야 합니다.

이 조건하에서 캐릭터가 최종적으로 도착할 수 있는 위치의 최댓값을 구하는 문제입니다.

문제에 적힌 내용을 조금 더 정확하게 이해해봅시다.

거울 사용시 위치를 문제에서 2b- a로 제시해주었고, 그림을 통해 확인해보면 다음과 같습니다.

• 시작 위치 0에서 1번 거울 사용: -2 위치로 이동 (2b-a = 2 x (-1) - 0 = -2)​
• -1 위치에서 2번 거울 사용: 6 위치로 이동 (2b-a = 2 x 2 - (-2) = 6)

위와 동일한 방식으로 2번 거울을 먼저 사용하고 1번 거울을 사용하면 캐릭터 최종 위치는 -6이 됩니다.

따라서 캐릭터 위치의 최대값은 1번 거울을 먼저 사용했을 때의 6이 됩니다.

💡 첫 번째 접근 - 모든 순서를 다 해보기?

가장 쉽게 떠오르는 방법은 어떤 거울을 먼저 쓸지 모든 순서를 다 바꿔가며 계산해 보는 것입니다.

이렇게 가능한 모든 경우의 수를 빠짐없이 전부 탐색하는 방식을 컴퓨터 공학 용어로 브루트포스(Brute-force, 완전 탐색)라고 부릅니다.

첫 번째 예제처럼 거울이 2개일 때는 (1번 거울 → 2번 거울), (2번 거울 → 1번 거울) 두 가지 경우만 계산해서 더 큰 값을 고르면 됩니다.

하지만 이 문제의 제약 조건을 살펴보면 거울의 수 N은 최대 200,000개입니다.

20만 개의 거울을 나열하는 경우의 수는 200,000!으로 슈퍼컴퓨터로도 제한 시간(1초) 내에 절대 계산할 수 없는 엄청난 숫자입니다.

따라서 이러한 접근 방식으로 코드를 작성했다면 시간초과로 인해 부분문제 1. N은 2 이하 에 해당하는 7점만 획득할 수 있습니다.

💻 코드 구현

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

if n == 1:
    print(2 * arr[0] - s)
elif n == 2:
    # 경우 1: 1번 거울 -> 2번 거울 순서
    pos1 = 2 * arr[1] - (2 * arr[0] - s)
    
    # 경우 2: 2번 거울 -> 1번 거울 순서
    pos2 = 2 * arr[0] - (2 * arr[1] - s)
    
    # 둘 중 더 큰 값을 출력
    print(max(pos1, pos2))

실전에서는 긴장감과 시간 압박 때문에, 평소에는 금방 찾아내던 수학적 규칙도 머릿속이 하얗게 변해 안 떠오를 때가 많습니다.

1년에 한 번 뿐인 대회, 그냥 포기하는 것보다는 내가 풀 수 있는 부분문제를 끈기있게 찾아내어 7점을 더 얻어내는 집념을 가져보세요.

3점 차이로 내가 받을 상이 달라질 수 있다

이렇게 단 몇 점 차이로 내가 받는 상이 달라질 수 있습니다.

정보올림피아드는 100점을 맞아야만 상을 받는 대회가 아닙니다.

이런 집념을 가지고 임하는 학생에게 다음 대회에서 더 좋은 아이디어가 피어날 것이라 믿습니다.

💡 두 번째 접근 - 수학적 규칙 찾기

컴퓨터가 모든 경우를 계산할 수 없다면, 우리가 직접 종이 위에서 수식의 패턴을 찾아내야 합니다.

거울을 차례대로 사용했을 때 위치가 어떻게 변하는지 수식으로 써보면 다음과 같습니다.

수식을 유심히 살펴보면 아주 중요한 규칙들을 발견할 수 있습니다.

1. 초기 위치 s는 거울의 개수가 짝수면 더해지고(+s), 홀수면 빼집니다(-s).
2. 선택한 거울의 위치(m)에는 항상 +2 또는 -2가 곱해집니다.

우리의 목표는 최종 위치의 값을 최대로 만드는 것입니다.

그렇다면 어떤 거울에 +2를 곱하고, 어떤 거울에 -2를 곱해야 결과가 가장 커질까요?

당연히 위치가 큰 거울들을 골라 더해주고, 위치가 작은 거울들을 골라 빼주면 됩니다.

문제에서 거울의 위치는 이미 오름차순으로 정렬되어 주어지기 때문에 중간을 기준으로 왼쪽, 오른쪽의 합을 계산하면 됩니다.

단, 홀수 위치일 때 보면 더해지는 쪽이 하나 더 많기 때문에 중간 위치는 오른쪽 합에 포함됩니다.

💻 코드 구현

n, s = map(int, input().split())
m = list(map(int, input().split())) # 거울
half = n // 2 # 거울 개수의 반

# 중간 위치는 큰 쪽에 포함
small = sum(m[:half]) # 작은 값들의 합
large = sum(m[half:]) # 큰 값들의 합

if n % 2 == 0: # 거울 개수가 짝수일 때는 +s
    print(2 * large - 2 * small + s)
else: # 거울 개수가 홀수일 때는 -s
    print(2 * large - 2 * small - s)

반복이 아니라 단순 연산으로 계산하기 때문에 거울의 개수가 20만 개라도 시간 내에 처리가 가능(100점)합니다.

📊 정답률

초등부에서는 약 30% 가량의 학생들이 100점을 받았고, 대부분의 학생들이 7점 풀이는 해낸 모습입니다.

중등부에서는 절반 이상이 100점, 90% 넘는 학생이 7점 이상을 획득했습니다.

3. 통행료 (초3)

추가 예정

4. 상자 보관 (초4)

추가 예정