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

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

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

1. 보물찾기 (초1)

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



📄 문제 개요

다빈이가 무한히 긴 수직선 위에서 보물을 찾는 놀이를 합니다. 보물은 왼쪽(L)과 오른쪽(R) 두 곳에 숨겨져 있고, 다빈이는 그 사이인 시작 위치(S)에서 출발합니다.

다빈이는 다음과 같은 규칙으로 이동합니다.

• 1단계: 제자리(S) 조사
• 2단계: 오른쪽으로 1칸 떨어진 곳(S+1) 조사
• 3단계: 왼쪽으로 1칸 떨어진 곳(S-1) 조사
• 4단계: 오른쪽으로 2칸 떨어진 곳(S+2) 조사
• ...

이 규칙대로 번갈아 가며 범위를 넓혀갈 때, 왼쪽(L)이나 오른쪽(R) 보물 중 가장 먼저 보물을 찾게 되는 단계를 구하는 문제입니다.  

💡 첫 번째 접근 - 직접 이동해보기

가장 직관적인 방법은 시작 위치(S)부터 한 단계씩 직접 움직여보면서 L 또는 R에 도착하는 상황을 확인하는 것입니다.

예를 들어 왼쪽 보물이 2(L=2), 오른쪽 보물이 9(R=9)에 있고 다빈이가 5(S=5)에서 출발한다고 가정해 보겠습니다.



이렇게 단계(step)를 1씩 늘려가며 짝수일 때는 오른쪽, 홀수일 때는 왼쪽을 확인하다가,

다빈이의 현재 위치가 L이나 R과 같아지면 반복을 멈추고 단계를 출력합니다. 

💻 코드 구현 - 하나씩 모두 비교하기

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    l, r, s = map(int, input().split())
    
    step = 1
    k = 0
    while True:
        # step이 짝수면 오른쪽(+k), 홀수면 왼쪽(-k)
        if step % 2 == 0:
            pos = s + k
        else:
            pos = s - k
            
        # 보물을 찾으면 종료
        if pos == l or pos == r:
            print(step)
            break
            
        # 다음 단계를 위한 설정
        step += 1
        if step % 2 == 0:
            k += 1

이 방식은 구현이 쉽다는 장점이 있지만, 제약 조건에 따라 보물이 시작점으로부터 1억 칸(100,000,000) 떨어져 있다면

반복문도 수억 번을 돌아야 합니다. 따라서 제한 시간 내에 모든 테스트 케이스를 통과하지 못하고 부분 점수(48점)를 받게 됩니다.

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

반복문으로 인한 시간 초과를 피하려면 종이 위에서 다빈이의 이동 패턴을 차분하게 수식으로 전개해 보아야 합니다.

단계

가장 중요한 핵심은 오른쪽, 왼쪽을 번갈아 가며 확인하기 때문에 두 단계를 거쳐야 어느 한 방향으로 한 칸씩 전진이 가능하다는 점입니다.

• 오른쪽 보물(R)을 찾는 규칙

오른쪽으로 1칸 전진하려면 (오른쪽) 👉 2단계 소요

오른쪽으로 2칸 전진하려면 (오른쪽, 왼쪽, 오른쪽) 👉 4단계 소요

오른쪽으로 떨어진 거리(R - S)를 가기 위해서는 두 단계씩 거쳐야 하므로 거리에 2를 곱하면 됩니다. 👉 수식: 2 * (R - S)

• 왼쪽 보물(L)을 찾는 규칙

왼쪽으로 1칸 전진하려면 (오른쪽, 왼쪽) 👉 3단계 소요

왼쪽으로 2칸 전진하려면 (오른쪽, 왼쪽, 오른쪽, 왼쪽) 👉 5단계 소요

항상 오른쪽을 먼저 확인한 뒤 왼쪽을 확인하기 때문에 왼쪽으로 떨어진 거리(S - L)에 2를 곱한 뒤, 처음에 썼던 1단계를 더해주면 됩니다.

👉 수식: 2 * (S - L) + 1

💻 코드 구현 - 카드 번호 처음 등장 위치 메모해두기

t = int(input())
for i in range(t):
    l, r, s = map(int, input().split())
    
    r_step = 2 * (r - s)  # 오른쪽 보물(R)을 찾는 단계
    l_step = 2 * (s - l) + 1 # 왼쪽 보물(L)을 찾는 단계
    
    # 둘 중 더 빨리 찾는(작은) 단계 출력
    print(min(r_step, l_step))

이렇게 수학적인 규칙을 찾아 수식을 잘 생각해내었다면 보물이 아주 멀리있더라도 단 한 번의 사칙연산으로 정답을 구할 수 있습니다.

따라서 제한 시간 내에 모든 테스트 케이스를 통과하고 100점을 받을 수 있습니다.



📊 정답률

2차에 진출한 80% 이상의 초등부 학생들이 100점을 받아낸 비교적 난이도가 쉬운 문제였습니다.

100점을 받지 못했더라도 거의 모든 학생들이 48점을 받을 수 있는 풀이는 해낸 모습입니다.

 

2. 가로등 (초2/중1/고1)

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

추가 예정

3. 색깔 모으기 (초3/중2)

추가 예정

4. 양손에 V (초4)

추가 예정