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

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

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

1. 불안정한 수열 (초1)

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

📄 문제 개요

N개의 자연수가 일렬로 주어집니다. 이 중에서 원하는 만큼 숫자를 골라 새로운 수열을 만들려고 합니다.

새로 만든 수열은 이웃한 두 숫자의 합이 무조건 홀수여야 합니다. 이를 불안정한 수열이라고 정의합니다.

이 조건을 만족하도록 숫자를 골랐을 때, 수열의 최대 길이를 구해야 합니다.

💡 문제 풀이 시뮬레이션

불안정한 수열은 이웃한 두 숫자의 합이 홀수여야 합니다.

숫자1	숫자2	두 수의 합	불안정 여부
짝수	짝수	짝수	X
홀수	홀수	짝수	X
짝수	홀수	홀수	O
홀수	짝수	홀수	O

위 표와 같이 두 수의 합이 홀수가 되려면 반드시 짝수와 홀수가 번갈아 가며 나와야 합니다.

우리가 해야할 일은 간단합니다. 주어진 배열을 돌면서 홀짝이 바뀌는 순간을 계속 카운트하면 불안정한 수열을 얻을 수 있습니다.

1. 불안정한 수열의 최대 길이를 구해야 하기 때문에 무조건 첫 번째 숫자는 고르고 시작합니다.
2. 다음 숫자들을 하나씩 확인하며, 이전 숫자와 홀짝이 다를 때만 그 숫자를 고릅니다.

💻 코드 구현

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

ans = 1  # 최대 길이를 구하기 위해 첫 번째 숫자는 고르고 시작

for i in range(n - 1):
    # 내 숫자(L[i])와 나 다음 숫자(L[i+1])의 홀짝성이 다르다면
    if L[i] % 2 != L[i+1] % 2:
        ans += 1  # 수열 길이 1 증가

print(ans)

수열을 한 바퀴 돌아보면서 나와 내 다음 숫자의 홀짝성이 다른 경우를 찾아보았습니다.

시간복잡도는 O(N)으로 주어진 N의 범위(1 <= N <= 300,000)를 계산하는데 충분합니다.

📊 정답률

2차에 진출한 초등부 학생들 중 80% 이상이 100점을 받은 문제였습니다.

일단 홀짝성을 비교해야겠다는 생각을 해내었다면 다양한 방법으로 풀이할 수 있는 난이도가 높지 않은 문제였습니다.



2. 스케이트 연습 (초2/중1/고1)

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

📄 문제 개요

N개의 체크포인트(중간 지점)가 있는 스케이트 코스가 있습니다.

• 출발점과 도착점에서의 속력은 반드시 0이어야 합니다.
• 각 체크포인트에는 넘어서는 안 되는 속력 제한(V)이 있습니다.
• 속력을 높일 때는 제한 없이 확 높일 수 있지만, 속력을 낮출 때는 직전 지점의 속력에서 딱 1만큼만 낮출 수 있습니다.
• 목표 : 조건을 지키며 코스를 완주할 때, 각 체크포인트에서 낼 수 있는 속력들의 총합의 최댓값을 구해야 합니다.



💡 문제 풀이 시뮬레이션

보통 문제를 풀 때 배열의 처음부터 끝으로 순서대로 탐색하는 것이 일반적입니다.

하지만 이 문제를 앞에서부터 탐색하게 되면 로직이 매우 복잡해집니다.

속력을 낮출 때는 1씩만 낮출 수 있다는 조건 때문에, 현재 위치에서 속력을 마음 편히 올리려면 앞으로 남은 모든 코스의 속력 제한을 미리 내다보고 계산해야 하기 때문입니다. 이런 상황에서는 탐색의 방향을 완전히 뒤집어 도착점부터 역방향으로 탐색해보는 것이 아주 좋은 해결책이 됩니다.

도착점부터 거꾸로 생각하면, 원래의 속력을 최대 1만 낮출 수 있다는 조건은 반대로 속력을 최대 1만 높일 수 있다는 단순한 조건으로 바뀝니다.

도착점의 속력은 무조건 0이기 때문에 도착 지점의 속력 0에서 시작합니다.

각 지점에서의 최대 속력은 ① 현재 지점의 속력 제한(V)과 ② 다음 지점의 속력 + 1 중 더 작은 값으로 단순하게 결정됩니다.



💻 코드 구현

import sys
input = sys.stdin.readline

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

speed = 0    # 현재 위치에서의 최대 속력 (도착점은 0이므로 0부터 시작)
ans = 0  # 낼 수 있는 속력들의 총합

# 배열의 맨 끝(도착점 직전)부터 첫 번째 지점까지 거꾸로 탐색
for i in range(n - 1, -1, -1):
    if speed < arr[i]: # 1. 내 속력을 1 높여도 속력 제한(arr[i])보다 작다면? 
        speed += 1  # 마음 편히 속력을 1 올림
        
    else: # 2. 내 속력을 1 높이면 속력 제한을 넘어가 버린다면?
        speed = arr[i]  # 해당 지점의 제한 속력에 맞춤
        
    ans += speed  # 결정된 속력을 정답에 누적

print(ans)

데이터의 개수 N이 최대 50만 개로 꽤 크지만, 이중 반복문 없이 배열을 거꾸로 한 번만 스캔(시간 복잡도 : O(N))하므로 2초의 시간 제한을 아주 여유롭게 통과합니다.



📊 정답률

100점을 받은 학생 비율이 초등부 50% 정도, 중등부 80% 이상, 고등부 90% 이상이었습니다.

초등부 학생들도 2번 문제치고는 난이도가 평이한 수준, 중/고등부에서는 반드시 맞춰야할 쉬운 문제였습니다.

참고로 풀어볼 만한 문제 링크를 하나 추가했으니, 시간이 나면 풀어보세요.

COCI 6회 "미래를 보는 투자자" 문제 풀이하러가기



3. 호숫가의 개미굴 (초3/중2)

추가 예정

4. 고기 파티 (초4/중3)

추가 예정