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

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

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

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

📄 문제 개요

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

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

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

💡 문제 풀이 시뮬레이션

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

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

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

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

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

💻 코드 구현

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)

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

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

추가 예정

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