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

아두위키 : Arduwiki
시각위키텍스트
(새 문서: {{#seo:|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이|title_mode=append|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2026 KOI, 2026 초등부 2차 대회, 거리두기, 주사위 탑 쌓기, 간식 분배, 게임, 정올 거리두기, 정올 주사위 탑 쌓기, 정올 간식 분배, 정올 게임|des...)
 
잔글편집 요약 없음
 
(같은 사용자의 중간 판 4개는 보이지 않습니다)
6번째 줄: 6번째 줄:




== '''[https://coj.ac/problems/2138 1. 장애물 (초1)]''' ==
== '''1. 거리두기 (초1)''' ==
제목 링크를 통해 문제를 확인해주세요.
추가 예정


=== 📄 문제 개요 ===
== '''2. 주사위 탑 쌓기 (초2, 중1)''' ==
수직선 위 위치 0에서 출발하여 N개의 장애물을 모두 뛰어넘어야 합니다.
추가 예정


* '''행동 1:''' 오른쪽으로 1만큼 걸어간다.
* '''행동 2:''' 오른쪽으로 2만큼 점프한다.
* '''장애물 넘기 규칙:''' 위치 X에 있는 장애물을 넘으려면, '''반드시 위치 X-1에서 점프하여 위치 X+1에 도착'''해야 합니다.


주어진 규칙을 활용해 '''모든 장애물을 넘기 위한 최소 이동 횟수'''를 구하고, 만약 넘는 것이 불가능하다면 '''-1'''을 출력하는 문제입니다.[[파일:2025KOI장애물1.png|center|class=coders100]]위 그림과 같이 한 칸, 혹은 두 칸을 움직여 최종적으로는 최소한의 움직임으로 모든 장애물을 넘어야 합니다.


== '''3. 간식 분배 (초3, 중2, 고1)''' ==


=== 💡 첫 번째 접근 - 문제 조건대로 하나씩 이동해보기 (Greedy) ===
=== 📄 문제 개요 ===
가장 확실하고 직관적인 방법은 캐릭터가 직접 이동하는 과정을 코드로 시뮬레이션해 보는 것입니다.


목적지(다음 장애물 앞 칸)까지 가장 적게 이동하려면  자연스럽게 1칸 걷기보다는 '''2칸 점프를 최대한 많이 활용'''해야 합니다.
* '''목표:''' N명의 학생이 순서대로 방에 들어가서 자신이 좋아하는 간식을 모두 가져갈 때, '''모든 학생이 정확히 1개의 간식만''' 가져가도록 하는 입장 순서를 찾아야 합니다. 불가능하다면 -1을 출력합니다.
* '''제약 조건:''' 학생 수(N)는 최대 200,000명입니다. 단순하게 모든 순서를 다 만들어보는 방식(순열)으로 접근하면 시간 초과가 발생합니다. 수십만 명의 학생을 빠르게 처리하기 위해서는 특정 조건에 맞는 학생들을 쏙쏙 골라내는 효율적인 자료구조가 필요합니다.


일단 이후는 생각하지 않고, '''현재 주어진 위치에서 최대한 앞으로 나가려고 하면''' 자연스럽게 정답에 도달할 수 있는 문제입니다.


이처럼 지금 당장 눈앞에 보이는 가장 효율적인 선택을 먼저 취하는 방식을 컴퓨터 공학에서는 '''<nowiki/>'그리디(Greedy, 탐욕) 알고리즘''''이라고 부릅니다.
=== 💡 문제 풀이 시뮬레이션 ===
가장 눈여겨볼 부분은 '''방에 들어가면 좋아하는 걸 다 가져간다'''는 규칙입니다. 만약 내가 좋아하는 간식이 3개인데 첫 번째로 방에 들어간다면 3개를 모두 가져가게 되어 '''정확히 1개'''라는 조건을 즉시 어기게 됩니다. 그렇다면 '''가장 먼저 방에 들어가야 할 사람'''은 누구일까요? 바로 '''현재 방에 남아있는 간식 중, 좋아하는 간식이 딱 1개뿐인 학생'''입니다. 좋아하는 간식이 1개 초과인 학생은 우선 순위가 될 수 없습니다.


[[파일:2025KOI장애물1.png|center|class=coders100]]
# 현재 좋아하는 간식이 '''딱 1개'''인 학생들을 찾아 줄을 세웁니다. (Queue의 형태)
# 줄 선 학생이 방에 들어가 간식을 가져갑니다.
# 간식이 하나 사라졌으므로, '''그 간식을 좋아했던 다른 학생들의 좋아하는 간식 개수'''가 1개씩 줄어듭니다.
# 간식이 하나 사라지면서 추가로 생긴 '''[좋아하는 간식이 딱 1개가 된 학생]'''을 고려하여 다시 줄을 세웁니다.
# 이 과정을 반복하여 N명이 모두 간식을 가져갔다면 성공, 중간에 멈췄다면 실패(-1)입니다.


* '''0 위치:''' 2칸 앞에 장애물이 있어 2칸을 가지 못하기 때문에 '''1칸 이동(0 → 1)'''
* '''1 위치:''' 2칸 앞에 장애물이 없기 때문에 '''2칸 이동(1 → 3)'''
* '''3 위치:''' 2칸 앞에 장애물이 있어 2칸을 가지 못하기 때문에 '''1칸 이동(3 → 4)'''
* '''4 위치:''' 2칸 앞에 장애물이 없기 때문에 '''2칸 이동(4 → 6)'''
* '''6 위치:''' 2칸 앞에 장애물이 없기 때문에 '''2칸 이동(6 → 8)'''​
* '''8 위치:''' 2칸 앞에 장애물이 없기 때문에 '''2칸 이동(8 → 10)'''
* '''10 위치:''' 2칸 앞에 장애물이 없기 때문에 '''2칸 이동(10 → 12), 모든 장애물 극복 완료'''


단, '''장애물 두 개가 붙어있는 경우'''(1칸 앞, 2칸 앞에 모두 장애물이 있는 경우)에는 장애물을 넘지 못한다는 사실을 기억해둡시다.
과정 자체는 어렵지 않지만 시간 복잡도를 만족하기 위해 자료를 정리해놓는 방식이 중요합니다.


실제 배열들이 어떻게 움직이며 꼬리에 꼬리를 물고 정답을 찾아내는지 '''예제 3번'''을 통해 자세히 추적해 보겠습니다.


=== 💻 코드 구현 ===
<syntaxhighlight lang="python3" line="1">
n = int(input())
arr = list(map(int, input().split()))


last = arr[-1] # 마지막 장애물 위치
'''[예제 3 입력]'''
x = [0] * (last + 2) # 장애물 위치 기록 / 마지막 장애물을 넘는 것을 고려하여 한 칸 넉넉하게
for i in arr:
    x[i] = 1


s = 0 # 현재 위치
* N = 4 (학생 4명, 간식 4개)
ans = 0
* 1번 학생 : 3번 간식 선호
while s < last: # 현 위치가 마지막 장애물보다 앞에 있는 동안
* 2번 학생 : 2번 간식 선호
    if x[s+2] == 0: # 2칸 앞에 장애물이 없다면 2칸 전진
* 3번 학생 : 4, 2, 3번 간식 선호
        s += 2
* 4번 학생 : 1, 2번 간식 선호
    elif x[s+1] == 0: # 1칸 앞에 장애물이 없다면 1칸 전진
        s += 1
    else: # 2칸 앞, 1칸 앞에 모두 장애물이 있으면 불가능
        ans = -1
        break
    ans += 1


print(ans)
</syntaxhighlight>이번 문제의 장애물 사이의 거리, 장애물의 개수가 최대 250,000이므로


이렇게 반복문으로 하나하나 시뮬레이션해도 시간초과 없이 안정적으로 100점을 받을 수 있습니다.
우선, 입력을 받으며 4개의 핵심 리스트를 만듭니다.


* cnt : 각 학생이 좋아하는 간식 중 '''남아있는 개수'''
* per : 각 학생이 좋아하는 '''간식 번호 리스트'''
* food : 각 간식을 좋아하는 '''학생 번호 리스트'''
* visit : 각 간식이 '''선택되었는지 여부''' (초기엔 모두 False)


=== 💡 두 번째 접근 - 수학적 접근 ===
{| class="wikitable" style="text-align: center;"
두 번째 방법은 이동해야할 거리에 따른 횟수를 수학적으로 계산하는 것입니다.
|-
! 번호(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]
|}




i위치에서 j까지 이동할 때, 두 지점 거리(d)는 j - i 입니다.
1~4번 학생 중 좋아하는 간식이 하나 뿐인 학생은 1, 2번 학생입니다.


이동할 때 최대한 '''2칸 점프를 많이 활용'''해야하기 때문에 가능한 만큼 먼저 점프를 활용합니다. (d // 2)
따라서 '''처음 큐(Queue)의 상태는 [1, 2]'''가 됩니다.


만약 도달하지 못하고 1칸이 남았다면 1칸 걷기를 더해 마무리합니다. (d % 2)
​


d % 2 값은 0 또는 1이기 때문에 2칸 점프로만 원하는 지점에 도착했더라도 '''최소 이동 횟수는 d // 2 + d % 2'''로 계산할 수 있습니다.
💡 '''[시뮬레이션 진행]'''


[[파일:2025KOI장애물2.png|center|class=coders100]]위에서 계산한 방식에 따라
▶️  '''1번 학생 입장 (현재 Queue: [2])'''


'''[0 → 1(+1)] + 장애물 뛰어넘기(+1) + [3 → 4(+1)] + 장애물 뛰어넘기(+1) + [6 → 10(+2)] + 장애물 뛰어넘기(+1) = 7'''
* '''행동 :''' 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)
<syntaxhighlight lang="python3" line="1">
* '''변화 :''' 2번 간식이 사라졌으므로, 2번 간식을 좋아하던 food[2] 리스트의 학생들(2번, 3번, 4번)의 cnt를 모두 1씩 줄입니다.
n = int(input())
* '''결과 :''' 2번 학생 cnt: 1 → 0, 3번 학생 cnt: 2 → 1 '''(1이 되었으니 큐에 추가)''', 4번 학생 cnt: 2 → 1 '''(1이 되었으니 큐에 추가)'''
obs = list(map(int, input().split()))
* 현재 정답 순서(ans): [1, 2], 대기열(Queue) : [3, 4]


s = 0 # 현재 위치
ans = 0


for i in obs:
▶️ '''3번 학생 입장 (현재 Queue: [4])'''
    # 장애물이 연속으로 붙은 경우 예외 처리
    if i - 1 < s:
        print(-1)
        exit()
   
    d = (i - 1) - s # 내 위치부터 다음 장애물 앞 칸까지 남은 거리
    ans += d / 2 + d % 2 # 최소 이동 횟수 누적
   
    # 장애물 뛰어넘기
    ans += 1
    s = i + 1
   
print(ans)
</syntaxhighlight>이번 문제의 경우 장애물 사이의 거리가 25만 칸으로 첫 번째 접근, 두 번째 접근의 시간 차이가 미미한 수준입니다.


하지만 '''장애물 사이의 거리가 10억 칸'''으로 늘어난다면 반복문으로 최대 2칸씩 이동하는 방법은 시간이 아주 오래 걸리게 됩니다.
* '''행동 :''' 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: [])'''


== '''[https://coj.ac/problems/2139 2. 거울 (초2/중1)]''' ==
* '''행동 :''' 4번 학생이 들어가서 남은 간식을 살핍니다. 2번은 사라졌으므로(visit 배열 확인) '''1번 간식'''만 챙깁니다. (visit[1] = True)
제목 링크를 통해 문제를 확인해주세요.
* '''변화 :''' 1번 간식이 사라졌으므로, food[1] 리스트의 학생(4번)의 cnt를 1 줄입니다.
* '''결과 :''' 4번 학생 cnt: 1 → 0
* 현재 정답 순서(ans): [1, 2, 3, 4], 대기열(Queue) : []


=== 📄 문제 개요 ===
수직선 위의 위치 s에서 출발하는 캐릭터가 있습니다. 그리고 수직선 위에는 N개의 거울이 놓여 있습니다.


* '''이동 규칙:''' 위치 a에 있는 캐릭터가 위치 b에 있는 거울을 사용하면, 거울을 기준으로 점대칭인 지점인 '''2b - a''' 위치로 이동하게 됩니다.
총 4명의 학생이 무사히(ans의 길이가 4) 모두 1개씩 간식을 챙겨갔습니다. 따라서 정답은 1 2 3 4가 됩니다.
* '''조건:''' N개의 거울을 '''원하는 순서대로 정확히 한 번씩 모두 사용'''해야 합니다.


이 조건하에서 캐릭터가 최종적으로 도착할 수 있는 위치의 '''최댓값'''을 구하는 문제입니다.
이 풀이는 그래프 이론의 '''위상 정렬(Topological Sorting)''' 개념을 응용한 것입니다. 순서가 정해져 있는 작업을 차례대로 수행할 때 사용하는 알고리즘으로, 진입 차수(이 문제에서는 좋아하는 간식의 수)가 조건에 맞는 노드(학생)부터 큐(Queue)에 넣어 처리하는 방식입니다. deque를 활용하여 '''O(N + 간식 선호도(C) 총합)'''의 시간 복잡도로 풀이 가능합니다.


[[파일:2025KOI거울1.png|center|class=coders100]]'''문제에 적힌 내용을 조금 더 정확하게 이해해봅시다.'''


거울 사용시 위치를 문제에서 2b- a로 제시해주었고, 그림을 통해 확인해보면 다음과 같습니다.
=== 💻 코드 구현 ===
<syntaxhighlight lang="python3" line="1">
from collections import deque
import sys
input = sys.stdin.readline


* '''시작 위치 0에서 1번 거울 사용: -2''' 위치로 이동 (2b-a  = 2 x (-1) - 0 = -2)​
N = int(input())
* '''-1 위치에서 2번 거울 사용: 6 위치'''로 이동 (2b-a = 2 x 2 - (-2) = 6)


# 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번 거울을 먼저 사용하고 1번 거울을 사용하면 캐릭터 최종 위치는 -6이 됩니다.
# 2. 초기 Queue 생성 : 좋아하는 간식이 1개인 학생들 추가
q = deque()
for i in range(1, N+1):
    if cnt[i] == 1:
        q.append(i)


따라서 캐릭터 위치의 최대값은 1번 거울을 먼저 사용했을 때의 6이 됩니다.
ans = []


 
# 3. 대기열 순회
=== 💡 첫 번째 접근 - 모든 순서를 다 해보기? ===
while q:
가장 쉽게 떠오르는 방법은 어떤 거울을 먼저 쓸지 '''모든 순서를 다 바꿔가며 계산'''해 보는 것입니다.
    c = q.popleft()
 
    if cnt[c] != 1: # cnt가 1이 아니면 모두 1개만 가져간다는 규칙을 어김.
이렇게 가능한 모든 경우의 수를 빠짐없이 전부 탐색하는 방식을 컴퓨터 공학 용어로 '''브루트포스(Brute-force, 완전 탐색)'''라고 부릅니다.
        break
 
 
 
첫 번째 예제처럼 거울이 2개일 때는 '''(1번 거울 → 2번 거울), (2번 거울 → 1번 거울)''' 두 가지 경우만 계산해서 더 큰 값을 고르면 됩니다.
 
하지만 이 문제의 제약 조건을 살펴보면 거울의 수 N은 최대 '''200,000개'''입니다.
 
20만 개의 거울을 나열하는 경우의 수는 200,000!으로 슈퍼컴퓨터로도 제한 시간(1초) 내에 절대 계산할 수 없는 엄청난 숫자입니다.
 
따라서 이러한 접근 방식으로 코드를 작성했다면 '''시간초과'''로 인해 '''부분문제 1.  N은 2 이하''' 에 해당하는 7점만 획득할 수 있습니다.
 
 
=== 💻 코드 구현 ===
<syntaxhighlight lang="python3" line="1">
n, s = map(int, input().split())
arr = list(map(int, input().split()))
 
if n == 1:
    print(2 * arr[0] - s)
elif n == 2:
    # 경우 1: 1번 거울 -> 2번 거울 순서
    pos1 = 2 * arr[1] - (2 * arr[0] - s)
      
      
     # 경우 2: 2번 거울 -> 1번 거울 순서
     ans.append(c) # 정답 순서에 추가
    pos2 = 2 * arr[0] - (2 * arr[1] - s)
      
      
     # 둘 중 더 큰 값을 출력
     # 해당 학생이 좋아하는 간식(하나를 제외한 나머지는 visit 처리가 되어있음)을 찾아 가져감
     print(max(pos1, pos2))
     for f in per[c]:
</syntaxhighlight>실전에서는 긴장감과 시간 압박 때문에, 평소에는 금방 찾아내던 수학적 규칙도 머릿속이 하얗게 변해 안 떠오를 때가 많습니다.
        if not visit[f]:
            visit[f] = True # 간식 가져감 처리
           
            # 이 간식을 좋아했던 다른 학생들의 cnt 감소
            for p in food[f]:
                cnt[p] -= 1
                # 카운트가 1이 된 학생이 있다면 새롭게 큐에 추가
                if cnt[p] == 1:
                    q.append(p)


1년에 한 번 뿐인 대회, 그냥 포기하는 것보다는 내가 풀 수 있는 부분문제를 끈기있게 찾아내어 7점을 더 얻어내는 집념을 가져보세요.
# 4. 모든 학생이 무사히 간식을 1개씩 가져갔는지 확인
 
if len(ans) == N:
[[파일:2025KOI거울3.png|center|class=coders100|3점 차이로 내가 받을 상이 달라질 수 있다]]
     print(*ans)
 
else:
이렇게 단 몇 점 차이로 내가 받는 상이 달라질 수 있습니다.
     print(-1)
 
 
정보올림피아드는 100점을 맞아야만 상을 받는 대회가 아닙니다.
 
이런 집념을 가지고 임하는 학생에게 다음 대회에서 더 좋은 아이디어가 피어날 것이라 믿습니다.
 
 
=== 💡 두 번째 접근 - 수학적 규칙 찾기 ===
컴퓨터가 모든 경우를 계산할 수 없다면, 우리가 직접 종이 위에서 수식의 패턴을 찾아내야 합니다.
 
거울을 차례대로 사용했을 때 위치가 어떻게 변하는지 수식으로 써보면 다음과 같습니다.
 
[[파일:2025KOI거울2.png|center|class=coders100]]수식을 유심히 살펴보면 아주 중요한 규칙들을 발견할 수 있습니다.
 
# 초기 위치 s는 거울의 개수가 짝수면 더해지고'''(+s)''', 홀수면 빼집니다'''(-s)'''.
# 선택한 거울의 위치(m)에는 항상 '''+2''' 또는 '''-2'''가 곱해집니다.
 
 
 
우리의 목표는 '''최종 위치의 값을 최대'''로 만드는 것입니다.
 
그렇다면 어떤 거울에 '''+2'''를 곱하고, 어떤 거울에 '''-2'''를 곱해야 결과가 가장 커질까요?
 
당연히 '''위치가 큰 거울들을 골라 더해주고, 위치가 작은 거울들을 골라 빼주면''' 됩니다.
 
문제에서 거울의 위치는 이미 오름차순으로 정렬되어 주어지기 때문에 '''중간을 기준'''으로 '''왼쪽, 오른쪽의 합'''을 계산하면 됩니다.
 
단, 홀수 위치일 때 보면 더해지는 쪽이 하나 더 많기 때문에 '''중간 위치는 오른쪽 합에 포함'''됩니다.
 
 
=== 💻 코드 구현 ===
<syntaxhighlight lang="python3" line="1">
n, s = map(int, input().split())
m = list(map(int, input().split())) # 거울
half = n // 2 # 거울 개수의 반
 
# 중간 위치는 큰 쪽에 포함
small = sum(m[:half]) # 작은 값들의 합
large = sum(m[half:]) # 큰 값들의 합
 
if n % 2 == 0: # 거울 개수가 짝수일 때는 +s
     print(2 * large - 2 * small + s)
else: # 거울 개수가 홀수일 때는 -s
     print(2 * large - 2 * small - s)
</syntaxhighlight>
</syntaxhighlight>


반복이 아니라 단순 연산으로 계산하기 때문에 거울의 개수가 20만 개라도 시간 내에 처리가 가능(100점)합니다.
== '''4. 게임 (초4, 중3)''' ==
 
 
== '''3. 통행료 (초3)''' ==
 
추가 예정
 
== '''4. 상자 보관 (초4)''' ==
추가 예정
추가 예정

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


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

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


1. 거리두기 (초1)

추가 예정

2. 주사위 탑 쌓기 (초2, 중1)

추가 예정


3. 간식 분배 (초3, 중2, 고1)

📄 문제 개요

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


💡 문제 풀이 시뮬레이션

가장 눈여겨볼 부분은 방에 들어가면 좋아하는 걸 다 가져간다는 규칙입니다. 만약 내가 좋아하는 간식이 3개인데 첫 번째로 방에 들어간다면 3개를 모두 가져가게 되어 정확히 1개라는 조건을 즉시 어기게 됩니다. 그렇다면 가장 먼저 방에 들어가야 할 사람은 누구일까요? 바로 현재 방에 남아있는 간식 중, 좋아하는 간식이 딱 1개뿐인 학생입니다. 좋아하는 간식이 1개 초과인 학생은 우선 순위가 될 수 없습니다.

  1. 현재 좋아하는 간식이 딱 1개인 학생들을 찾아 줄을 세웁니다. (Queue의 형태)
  2. 줄 선 학생이 방에 들어가 간식을 가져갑니다.
  3. 간식이 하나 사라졌으므로, 그 간식을 좋아했던 다른 학생들의 좋아하는 간식 개수가 1개씩 줄어듭니다.
  4. 간식이 하나 사라지면서 추가로 생긴 [좋아하는 간식이 딱 1개가 된 학생]을 고려하여 다시 줄을 세웁니다.
  5. 이 과정을 반복하여 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)

추가 예정

원본 주소 "https://arduwiki.com/html/index.php?title=2026_한국정보올림피아드(KOI)_2차_대회_초등부&oldid=2985"