2026 한국정보올림피아드(KOI) 2차 대회 초등부: 두 판 사이의 차이

시각위키텍스트

2026년 8월 12일 (수) 02:09 기준 최신판

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

1. 거리두기 (초1)

추가 예정

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)

추가 예정

@@ 20번째 줄: / 20번째 줄: @@
 * '''목표:''' N명의 학생이 순서대로 방에 들어가서 자신이 좋아하는 간식을 모두 가져갈 때, '''모든 학생이 정확히 1개의 간식만''' 가져가도록 하는 입장 순서를 찾아야 합니다. 불가능하다면 -1을 출력합니다.
 * '''제약 조건:''' 학생 수(N)는 최대 200,000명입니다. 단순하게 모든 순서를 다 만들어보는 방식(순열)으로 접근하면 시간 초과가 발생합니다. 수십만 명의 학생을 빠르게 처리하기 위해서는 특정 조건에 맞는 학생들을 쏙쏙 골라내는 효율적인 자료구조가 필요합니다.
 === 💡 문제 풀이 시뮬레이션 ===