2026 한국정보올림피아드(KOI) 2차 대회 초등부
한국 정보올림피아드(KOI) 기출 문제 풀이과정을 수록합니다.
1. 거리두기 (초1)
📄 문제 개요
N명의 학생이 1번부터 N번까지 번호 순서대로 수직선 위에 서려고 합니다.
각 학생이 서는 위치를 Bi라고 할 때 다음 두 조건을 만족해야 합니다.
- 위치 제한: i번 학생은 Ai보다 오른쪽에 설 수 없습니다. 즉, Bi ≤ Ai입니다.
- 거리 제한: 번호가 연속한 두 학생은 K 이상의 거리를 두어야 합니다. 즉, Bi+1 - Bi ≥ K입니다.
- 목표: 모든 조건을 만족하면서 1번 학생의 위치 B1을 최대한 크게 만들어야 합니다.
학생의 위치는 정수이며, 음수도 가능합니다. K=0이면 여러 학생이 같은 위치에 서도 됩니다.
💡 문제 풀이 시뮬레이션
처음에는 각 학생을 자신이 설 수 있는 가장 오른쪽 위치인 Ai에 배치하는 방법을 생각할 수 있습니다.
하지만 A의 값들이 K 이상의 간격으로 정렬되어 있다는 보장이 없습니다.
예제 1을 보겠습니다.
N = 5, K = 2, A = [1, 4, 10, 9, 13]
모든 학생을 Ai에 세우면 3번 학생의 위치는 10, 4번 학생의 위치는 9가 됩니다.
번호가 뒤인 4번 학생이 오히려 왼쪽에 있으므로 당연히 조건을 만족하지 않습니다. 이 문제에서 중요한 것은 위치를 정하는 방향입니다.
1번 학생부터 오른쪽으로 이동하며 위치를 정하면, 아직 확인하지 않은 뒤쪽 학생의 A 값 때문에 앞에서 정한 위치를 다시 수정해야 할 수 있습니다.
반대로 마지막 학생부터 보면, 바로 오른쪽 학생의 위치를 이미 알고 있으므로 현재 학생이 설 수 있는 가장 오른쪽 위치를 바로 결정할 수 있습니다.
📌 마지막 학생부터 위치 정하기
마지막 N번 학생의 오른쪽에는 다른 학생이 없습니다. 따라서 N번 학생은 자신이 설 수 있는 가장 오른쪽 위치인 AN에 배치합니다.
B_N = A_N
이제 i번 학생의 바로 오른쪽에 있는 i+1번 학생의 위치가 정해졌다고 생각해 보겠습니다.
i번 학생이 지켜야 할 조건은 두 가지입니다.
- Bi ≤ Ai
- Bi ≤ Bi+1 - K
따라서 두 조건을 모두 만족하는 가장 큰 위치는 다음과 같습니다.
B_i = min(A_i, B_(i+1) - K)
Ai에 그대로 서도 오른쪽 학생과 K 이상 거리가 확보된다면 Ai에 서고, 거리가 K보다 작아진다면 오른쪽 학생의 위치에서 K를 뺀 곳에 서야 합니다.
📌 예제 1에 적용하기
N = 5, K = 2, A = [1, 4, 10, 9, 13]
- 먼저, 5번 학생의 위치는 가장 오른쪽인 A5가 됩니다.
A5 = B5 = 13 - 4번 학생이 A4 = 9에 서면 5번 학생과의 거리는 4입니다. K=2 이상이므로 그대로 9에 설 수 있습니다.
B4 = min(9, 13-2) = 9 - 3번 학생은 A3 = 10에 설 수 없습니다. 4번 학생의 위치가 9이므로 7 이하에 서야 2 이상의 거리를 확보할 수 있습니다.
B3 = min(10, 9-2) = 7 - 같은 방법으로 2번과 1번 학생의 위치도 정합니다.
B2 = min(4, 7-2) = 4
B1 = min(1, 4-2) = 1
최종 위치는 다음과 같습니다.
| 학생 번호 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 위치 | 1 | 4 | 7 | 9 | 13 |
문제에 제시된 예제 출력은 1 4 6 9 12이지만, 반드시 예제와 같은 위치를 출력할 필요는 없습니다.
두 결과 모두 B1 = 1이며 모든 위치 제한과 거리 조건을 만족합니다. 가능한 답이 여러 개라면 그중 아무거나 출력해도 정답으로 인정합니다.
📌 왜 각 학생을 가장 오른쪽에 세워야 할까?
뒤에 서 있는 학생이 최대한 오른쪽으로 붙어서 왼쪽에 공간을 크게 만들어주면, 앞 학생들도 최대한 오른쪽으로 붙을 수 있게 됩니다.
우리가 최대화해야 하는 값은 가장 왼쪽에 있는 1번 학생의 위치입니다. 따라서 오른쪽 학생부터 차례대로 가능한 가장 오른쪽 위치에 세워야 B1도 최대한 오른쪽으로 보낼 수 있습니다.
이 과정을 N번 학생부터 1번 학생까지 한 번만 진행하므로 시간 복잡도는 O(N)입니다.
💻 코드 구현
N, K = map(int, input().split())
arr = list(map(int, input().split()))
# 마지막 학생부터 위치를 정하므로 ans에는 학생들의 위치가 역순으로 저장됩니다.
ans = [arr[-1]]
for i in range(N-2, -1, -1):
# 현재 학생이 A_i에 서도 K 이상의 거리를 확보할 수 있는 경우
if ans[-1] - arr[i] >= K:
ans.append(arr[i])
# 거리가 부족하면 오른쪽 학생보다 K만큼 왼쪽에 배치
else:
ans.append(ans[-1] - K)
# 역순으로 저장된 위치를 1번 학생부터 출력
for i in range(N-1, -1, -1):
print(ans[i], end=" ")
2. 주사위 탑 쌓기 (초2, 중1)
추가 예정
3. 간식 분배 (초3, 중2, 고1)
📄 문제 개요
- 목표: N명의 학생이 순서대로 방에 들어가서 자신이 좋아하는 간식을 모두 가져갈 때, 모든 학생이 정확히 1개의 간식만 가져가도록 하는 입장 순서를 찾아야 합니다. 불가능하다면 -1을 출력합니다.
- 제약 조건: 학생 수(N)는 최대 200,000명입니다. 단순하게 모든 순서를 다 만들어보는 방식(순열)으로 접근하면 시간 초과가 발생합니다. 수십만 명의 학생을 빠르게 처리하기 위해서는 특정 조건에 맞는 학생들을 쏙쏙 골라내는 효율적인 자료구조가 필요합니다.
💡 문제 풀이 시뮬레이션
가장 눈여겨볼 부분은 방에 들어가면 좋아하는 걸 다 가져간다는 규칙입니다. 만약 내가 좋아하는 간식이 3개인데 첫 번째로 방에 들어간다면 3개를 모두 가져가게 되어 정확히 1개라는 조건을 즉시 어기게 됩니다. 그렇다면 가장 먼저 방에 들어가야 할 사람은 누구일까요? 바로 현재 방에 남아있는 간식 중, 좋아하는 간식이 딱 1개뿐인 학생입니다. 좋아하는 간식이 1개 초과인 학생은 우선 순위가 될 수 없습니다.
- 현재 좋아하는 간식이 딱 1개인 학생들을 찾아 줄을 세웁니다. (Queue의 형태)
- 줄 선 학생이 방에 들어가 간식을 가져갑니다.
- 간식이 하나 사라졌으므로, 그 간식을 좋아했던 다른 학생들의 좋아하는 간식 개수가 1개씩 줄어듭니다.
- 간식이 하나 사라지면서 추가로 생긴 [좋아하는 간식이 딱 1개가 된 학생]을 고려하여 다시 줄을 세웁니다.
- 이 과정을 반복하여 N명이 모두 간식을 가져갔다면 성공, 중간에 멈췄다면 실패(-1)입니다.
과정 자체는 어렵지 않지만 시간 복잡도를 만족하기 위해 자료를 정리해놓는 방식이 중요합니다.
실제 배열들이 어떻게 움직이며 꼬리에 꼬리를 물고 정답을 찾아내는지 예제 3번을 통해 자세히 추적해 보겠습니다.
[예제 3 입력]
- N = 4 (학생 4명, 간식 4개)
- 1번 학생 : 3번 간식 선호
- 2번 학생 : 2번 간식 선호
- 3번 학생 : 4, 2, 3번 간식 선호
- 4번 학생 : 1, 2번 간식 선호
우선, 입력을 받으며 4개의 핵심 리스트를 만듭니다.
- cnt : 각 학생이 좋아하는 간식 중 남아있는 개수
- per : 각 학생이 좋아하는 간식 번호 리스트
- food : 각 간식을 좋아하는 학생 번호 리스트
- visit : 각 간식이 선택되었는지 여부 (초기엔 모두 False)
| 번호(i) | cnt (남은 간식 수) | per (좋아하는 간식) | food (이 간식을 좋아하는 학생들) |
|---|---|---|---|
| 1 | 1개 | [3] | 1번 간식: [4] |
| 2 | 1개 | [2] | 2번 간식: [2, 3, 4] |
| 3 | 3개 | [4, 2, 3] | 3번 간식: [1, 3] |
| 4 | 2개 | [1, 2] | 4번 간식: [3] |
1~4번 학생 중 좋아하는 간식이 하나 뿐인 학생은 1, 2번 학생입니다.
따라서 처음 큐(Queue)의 상태는 [1, 2]가 됩니다.
💡 [시뮬레이션 진행]
▶️ 1번 학생 입장 (현재 Queue: [2])
- 행동 : 1번 학생이 들어가서 3번 간식을 챙깁니다. (visit[3] = True)
- 변화 : 3번 간식이 사라졌으므로, 3번 간식을 좋아하던 food[3] 리스트의 학생들(1번, 3번)의 cnt를 1씩 줄입니다.
- 결과 : 1번 학생 cnt: 1 → 0, 3번 학생 cnt: 3 → 2 (아직 1개가 아니므로 대기)
- 현재 정답 순서(ans): [1], 대기열(Queue) : []
▶️ 2번 학생 입장 (현재 Queue: [])
- 행동 : 2번 학생이 들어가서 2번 간식을 챙깁니다. (visit[2] = True)
- 변화 : 2번 간식이 사라졌으므로, 2번 간식을 좋아하던 food[2] 리스트의 학생들(2번, 3번, 4번)의 cnt를 모두 1씩 줄입니다.
- 결과 : 2번 학생 cnt: 1 → 0, 3번 학생 cnt: 2 → 1 (1이 되었으니 큐에 추가), 4번 학생 cnt: 2 → 1 (1이 되었으니 큐에 추가)
- 현재 정답 순서(ans): [1, 2], 대기열(Queue) : [3, 4]
▶️ 3번 학생 입장 (현재 Queue: [4])
- 행동 : 3번 학생이 들어가서 남은 간식을 살핍니다. 2번, 3번 간식은 이미 사라졌으므로(visit 배열 확인) 4번 간식만 챙깁니다. (visit[4] = True)
- 변화 : 4번 간식이 사라졌으므로, food[4] 리스트의 학생(3번)의 cnt를 1 줄입니다.
- 결과 : 3번 학생 cnt: 1 → 0
- 현재 정답 순서(ans): [1, 2, 3], 대기열(Queue) : [4]
▶️ 4번 학생 입장 (현재 Queue: [])
- 행동 : 4번 학생이 들어가서 남은 간식을 살핍니다. 2번은 사라졌으므로(visit 배열 확인) 1번 간식만 챙깁니다. (visit[1] = True)
- 변화 : 1번 간식이 사라졌으므로, food[1] 리스트의 학생(4번)의 cnt를 1 줄입니다.
- 결과 : 4번 학생 cnt: 1 → 0
- 현재 정답 순서(ans): [1, 2, 3, 4], 대기열(Queue) : []
총 4명의 학생이 무사히(ans의 길이가 4) 모두 1개씩 간식을 챙겨갔습니다. 따라서 정답은 1 2 3 4가 됩니다.
이 풀이는 그래프 이론의 위상 정렬(Topological Sorting) 개념을 응용한 것입니다. 순서가 정해져 있는 작업을 차례대로 수행할 때 사용하는 알고리즘으로, 진입 차수(이 문제에서는 좋아하는 간식의 수)가 조건에 맞는 노드(학생)부터 큐(Queue)에 넣어 처리하는 방식입니다. deque를 활용하여 O(N + 간식 선호도(C) 총합)의 시간 복잡도로 풀이 가능합니다.
💻 코드 구현
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
# cnt[i]: i번 학생이 현재 좋아하는 간식 중 남아있는 개수
cnt = [0 for _ in range(N+1)]
# per[i]: i번 학생이 좋아하는 간식들의 리스트
per = [0]
# food[j]: j번 간식을 좋아하는 학생들의 리스트
food = [[] for _ in range(N+1)]
# visit[j]: j번 간식이 누군가에게 선택되었는지 여부
visit = [False for _ in range(N+1)]
# 1. 필요한 데이터 준비
for i in range(1, N+1):
a = list(map(int, input().split()))
cnt[i] = a[0]
per.append(a[1:])
for j in range(1, len(a)):
food[a[j]].append(i) # 이 간식을 좋아하는 학생 기록
# 2. 초기 Queue 생성 : 좋아하는 간식이 1개인 학생들 추가
q = deque()
for i in range(1, N+1):
if cnt[i] == 1:
q.append(i)
ans = []
# 3. 대기열 순회
while q:
c = q.popleft()
if cnt[c] != 1: # cnt가 1이 아니면 모두 1개만 가져간다는 규칙을 어김.
break
ans.append(c) # 정답 순서에 추가
# 해당 학생이 좋아하는 간식(하나를 제외한 나머지는 visit 처리가 되어있음)을 찾아 가져감
for f in per[c]:
if not visit[f]:
visit[f] = True # 간식 가져감 처리
# 이 간식을 좋아했던 다른 학생들의 cnt 감소
for p in food[f]:
cnt[p] -= 1
# 카운트가 1이 된 학생이 있다면 새롭게 큐에 추가
if cnt[p] == 1:
q.append(p)
# 4. 모든 학생이 무사히 간식을 1개씩 가져갔는지 확인
if len(ans) == N:
print(*ans)
else:
print(-1)
4. 게임 (초4, 중3)
추가 예정