2 - 2021 KOI 1교시 중등부 풀이 정리

2021 KOI 1교시 중등부 풀이 정리

이 문서는 2021 - 중등부 기출문제를 바탕으로, 정답 자료를 중학생 기준의 학습용 풀이로 다시 정리한 문서입니다. 계산형은 직접 검산한 식을 넣었고, 그림형·구성형은 공식 예시를 따라가며 핵심 아이디어를 설명했습니다.

1. 다른 모자 쓰기

문제 한눈에 보기

4명이 모두 자기 모자 말고 다른 모자를 쓰는 경우의 수를 구하는 문제입니다.

답

$9$

핵심 개념

이 문제는 derangement의 가장 기본 예입니다.

왜 이 생각을 먼저 해야 하는지

전체 경우에서 “제자리인 사람”을 포함배제로 빼면 가장 빠릅니다.

단계별 풀이

1. 전체는 $4!=24$가지입니다.
2. 포함배제를 적용하면
   $24-C(4,1)3!+C(4,2)2!-C(4,3)1!+C(4,4)0!$
3. 계산하면 $24-24+12-4+1=9$입니다.

헷갈리기 쉬운 점

한 사람만 제자리인 경우를 뺄 때, 두 사람도 제자리인 경우가 중복되어 빠집니다.

2. 상금배분

문제 한눈에 보기

7전 4선승제에서 A팀이 2승 0패로 앞선 상태에서 남은 우승 확률 비율대로 상금을 나누는 문제입니다.

답

$13$억원

핵심 개념

A의 우승 확률을 먼저 구하고, 16억원에 곱하면 됩니다.

왜 이 생각을 먼저 해야 하는지

공정한 분배는 “현재까지가 아니라 앞으로 우승할 확률”에 비례해야 하기 때문입니다.

단계별 풀이

1. A는 앞으로 $2$승, B는 $4$승이 더 필요합니다.
2. B가 우승하려면 A가 2승 하기 전에 먼저 4승해야 합니다.
3. B 우승 경우는
   BBBB 또는 ABBBB, BABBB, BBABB, BBBAB의 5가지 패턴입니다.
4. 확률은 $1/16+4/32=1/16+1/8=3/16$입니다.
5. 따라서 A 우승 확률은 $13/16$이고, 상금은 $16\times 13/16=13$억원입니다.

헷갈리기 쉬운 점

남은 경기 수가 5경기라고 해서 단순히 5경기 중 A가 몇 번 이기나로 세면 안 됩니다. 시리즈는 중간에 끝날 수 있습니다.

3. 함수값 구하기

문제 한눈에 보기

재귀식으로 정의된 함수 $f(n)$에 대해 $f(2049)$를 구하는 문제입니다.

답

$23$

핵심 개념

홀수면 $+1$, 짝수면 $/2$를 반복해 결국 $1$로 가는 데 걸리는 횟수를 세는 문제입니다.

왜 이 생각을 먼저 해야 하는지

식만 보면 복잡하지만, 실제로는 정해진 규칙대로 수를 줄여 가는 과정입니다.

단계별 풀이

1. $2049$는 홀수이므로 $2049\to 2050$ 한 번.
2. $2050$은 짝수이므로 $1025$로 줄어듭니다.
3. 같은 식으로
   $1025\to 1026\to 513\to 514\to 257\to 258\to \cdots \to 3\to 4\to 2\to 1$
4. 전체 이동 횟수를 세면 $23$번입니다.

헷갈리기 쉬운 점

홀수일 때는 $-1$이 아니라 $+1$입니다.

4. 동전과 확률

문제 한눈에 보기

10개 동전 중 $x$개만 뒷면에 A가 적혀 있을 때, 두 개를 골라 둘 다 A가 나올 확률이 $0.4$ 이하가 되게 하는 최대 $x$를 구하는 문제입니다.

답

$6$

핵심 개념

확률은 조합으로 $C(x,2)/C(10,2)$입니다.

왜 이 생각을 먼저 해야 하는지

두 개를 한 번에 고르므로 순서가 없습니다.

단계별 풀이

1. 전체 두 개 선택은 $C(10,2)=45$가지입니다.
2. 둘 다 A일 경우는 $C(x,2)$가지입니다.
3. 따라서
   $C(x,2)/45\le 0.4$
4. 즉 $x(x-1)/2\le 18$입니다.
5. $x=6$이면 $15\le 18$, $x=7$이면 $21>18$입니다.
6. 따라서 최대값은 $6$입니다.

헷갈리기 쉬운 점

$x/10\times (x-1)/9$로 써도 되지만, 조합으로 쓰면 더 깔끔합니다.

5. 물통

문제 한눈에 보기

3L 물통과 7L 물통으로 1L부터 7L까지 모두 만들 수 있는지 묻는 문제입니다.

답

1L, 2L, 3L, 4L, 5L, 6L, 7L 모두 만들 수 있다.

핵심 개념

$\gcd (3,7)=1$이므로 1L를 만들 수 있고, 그러면 모든 양을 만들 수 있습니다.

왜 이 생각을 먼저 해야 하는지

최대공약수가 1인 두 물통 문제는 작은 단위까지 만들 수 있다는 게 핵심입니다.

단계별 풀이

1. 7L를 채워 3L에 부으면 7L 통에 $4$L가 남습니다.
2. 4L를 다시 3L에 부으면 7L 통에 $1$L가 남습니다.
3. 이렇게 $1$L, $3$L, $4$L, $7$L를 만들 수 있습니다.
4. 나머지는 $2=3-1$, $5=4+1$, $6=7-1$처럼 얻습니다.

헷갈리기 쉬운 점

눈금이 없더라도 “가득 참”과 “비어 있음”을 이용하면 필요한 차이가 남습니다.

6. 2의 100제곱

문제 한눈에 보기

$2^{100}$의 10의 자리 숫자를 구하는 문제입니다.

답

$7$

핵심 개념

10의 자리는 $\mathrm{mod}100$으로 보면 됩니다.

왜 이 생각을 먼저 해야 하는지

마지막 두 자리만 알면 10의 자리는 바로 읽을 수 있습니다.

단계별 풀이

1. $2^{100}\mathrm{mod}100$을 구합니다.
2. 계산하면 $2^{100}\equiv 76(\mathrm{mod}100)$입니다.
3. 따라서 10의 자리는 $7$입니다.

헷갈리기 쉬운 점

일의 자리 주기만 보면 10의 자리는 알 수 없습니다.

7. 경로조정하기

문제 한눈에 보기

이진 트리의 일부 간선 가중치를 늘려서, 루트에서 모든 잎까지의 경로 길이를 같게 만들 때 증가량 총합의 최소를 구하는 문제입니다.

답

$33$

핵심 개념

아래에서 위로 올라오며 각 노드의 두 자식 경로 길이를 맞추면 됩니다.

왜 이 생각을 먼저 해야 하는지

위에서 먼저 맞추면 아래에서 다시 어긋날 수 있습니다. 리프 쪽부터 정리해야 합니다.

단계별 풀이

1. 각 노드에서 왼쪽·오른쪽 자식 쪽의 최대 경로 길이를 계산합니다.
2. 더 짧은 쪽에 필요한 만큼 가중치를 더해 둘을 같게 만듭니다.
3. 이 값을 모든 내부 노드에 대해 더한 것이 최소 증가량입니다.
4. 그림의 트리에 적용하면 총 증가량은 $33$입니다.

헷갈리기 쉬운 점

각 노드에서 “현재까지의 최대 길이”를 기준으로 짧은 쪽만 늘려야 최소입니다.

8. 과일박스 찾기

문제 한눈에 보기

6개 박스 중 라벨이 정확한 것은 정확히 1개뿐일 때, 최악의 경우 몇 개를 열어야 그 박스를 찾을 수 있는지 묻는 문제입니다.

답

$4$

핵심 개념

틀린 라벨을 확인하는 것도 정보입니다.

왜 이 생각을 먼저 해야 하는지

이 문제는 정확한 박스를 맞히는 문제지, 모든 박스 내용을 전부 맞히는 문제가 아닙니다.

단계별 풀이

1. 4개를 열면, 그중 정확한 라벨이 나오면 끝입니다.
2. 만약 4개가 모두 틀리면 남은 2개 중 정확한 라벨은 정확히 1개여야 합니다.
3. 이미 확인한 과일과 남은 라벨을 비교하면 어느 쪽이 맞는지 결정할 수 있습니다.
4. 3개만 열어서는 남은 3개가 여러 경우로 남아 최악의 경우 못 정합니다.

헷갈리기 쉬운 점

열어서 틀린 것을 확인하는 순간, 남은 경우 수가 크게 줄어듭니다.

9. 돌 무더기게임

문제 한눈에 보기

세 무더기 돌이 $1,2,3$개일 때 번갈아 돌을 가져가며 마지막 돌을 가져가는 사람이 이기는 게임입니다.

답

B가 항상 승리한다.

핵심 개념

이 게임은 기본적인 Nim이고, 시작 상태의 님합이 $0$입니다.

왜 이 생각을 먼저 해야 하는지

Nim에서는 님합이 $0$인 상태가 losing state라는 사실이 핵심입니다.

단계별 풀이

1. 시작 님합은 $1\mathrm{xor}2\mathrm{xor}3=0$입니다.
2. 님합이 0이면 현재 차례 플레이어는 불리합니다.
3. A가 어떤 수를 가져가면 님합이 0이 아닌 상태가 됩니다.
4. 그러면 B는 다시 님합 0으로 돌려놓는 대응을 할 수 있습니다.
5. 따라서 최적 플레이에서는 B가 이깁니다.

헷갈리기 쉬운 점

돌 총개수가 아니라 각 무더기 크기의 xor가 중요합니다.

10. 숫자 추측

문제 한눈에 보기

정사면체를 두 번 던져 나온 바닥 수 $a\le b$의 합과 곱을 듣고 대화를 나눈 뒤, $a^2+b^2$를 구하는 문제입니다.

답

$17$

핵심 개념

대화 한 줄마다 가능한 $(a,b)$ 후보를 지워 나가면 됩니다.

왜 이 생각을 먼저 해야 하는지

합과 곱만으로는 후보가 여러 개라서, “누가 알고 모르는지”가 추가 조건이 됩니다.

단계별 풀이

1. 가능한 쌍은 $(1,1)$부터 $(4,4)$까지의 $a\le b$ 경우입니다.
2. “곱만 듣고는 모른다”에서 곱이 하나로 정해지는 경우를 제거합니다.
3. “합을 듣고 이제는 안다”에서 남은 후보 중 합이 하나뿐인 경우로 좁힙니다.
4. 그 뒤 조건들을 차례로 적용하면 가능한 쌍은 $(1,4)$만 남습니다.
5. 따라서 $a^2+b^2=1^2+4^2=17$입니다.

헷갈리기 쉬운 점

대화 조건은 한 번만 적용하는 게 아니라, 앞 대화에서 줄어든 후보 집합 위에서 계속 갱신해야 합니다.

11. 중심 노드 찾기

문제 한눈에 보기

한 노드는 모든 다른 노드로 향하는 간선을 갖고, 자신으로 들어오는 간선은 전혀 없습니다. 이 중심 노드를 찾기 위한 query 최소 횟수를 묻는 문제입니다.

답

$n-1$

핵심 개념

한 번 비교할 때마다 중심 후보를 적어도 하나는 탈락시킬 수 있습니다.

왜 이 생각을 먼저 해야 하는지

후보를 줄이는 문제로 보면 상한과 하한이 동시에 잘 보입니다.

단계별 풀이

1. 두 노드 $a,b$를 비교해 $a\to b$가 있으면 $b$는 중심 노드가 될 수 없습니다.
2. 반대로 간선이 없으면 $a$는 중심 노드가 될 수 없습니다.
3. 즉 query 한 번으로 후보 하나를 지울 수 있습니다.
4. 후보가 $n$개이므로 $n-1$번이면 후보를 하나로 줄일 수 있습니다.
5. 이보다 적게는 모든 후보를 구별할 수 없으므로 최소도 $n-1$입니다.

헷갈리기 쉬운 점

중심 노드는 “모든 곳으로 나가는” 노드이지, 많이 연결된 일반 허브 노드가 아닙니다.

12. 두번 이상 지나는 경로 세기

문제 한눈에 보기

오른쪽/아래로만 가는 경로 중에서, ● 표시를 2군데 이상 지나는 경로 수를 구하는 문제입니다.

답

$53$

핵심 개념

격자 경로 수는 DP로 세고, “몇 개의 ●를 지났는지”까지 상태에 넣으면 됩니다.

왜 이 생각을 먼저 해야 하는지

경로를 직접 나열하면 너무 많으므로, 각 칸까지 오는 방법 수를 누적해야 합니다.

단계별 풀이

1. 각 칸에 대해 “●를 0개, 1개, 2개 이상 지나서 오는 경로 수”를 따로 둡니다.
2. 왼쪽과 위쪽에서 오는 값을 더해 DP를 진행합니다.
3. X 칸은 0으로 막고, ● 칸에 오면 상태를 한 단계 올립니다.
4. 도착점에서 “2개 이상” 상태의 값이 $53$입니다.

헷갈리기 쉬운 점

●를 정확히 2개가 아니라 “2개 이상”입니다.

13. 첫 월급

문제 한눈에 보기

선물 상자 10개를 1개 175원, 3개 400원, 5개 700원 조건으로 최소 비용에 사는 문제입니다.

답

$1375$원

핵심 개념

단가를 비교하면 5개 묶음보다 3개 묶음이 더 유리합니다.

왜 이 생각을 먼저 해야 하는지

묶음 가격 문제는 먼저 1개당 가격을 보면 좋은 묶음이 보입니다.

단계별 풀이

1. 단가는 1개 175원, 3개 약 133.3원, 5개 140원입니다.
2. 가장 좋은 묶음은 3개 400원입니다.
3. 10개를 만들기 위해 $3+3+3+1$로 사면 총 $400\times 3+175=1375$원입니다.
4. 다른 조합보다 이 값이 가장 작습니다.

헷갈리기 쉬운 점

가장 큰 묶음이라고 항상 가장 싸지는 않습니다.

14. 하노이의 탑

문제 한눈에 보기

원판을 옮길 때 $1\to 2$, $2\to 3$, $3\to 1$ 방향만 허용되는 하노이의 탑 변형 문제입니다.

답

PDF의 예시 순서대로 41번 이동하면 된다.

핵심 개념

방향 제한이 있으므로 일반 하노이처럼 아무 막대로 바로 못 옮깁니다.

왜 이 생각을 먼저 해야 하는지

가장 큰 원판 하나를 옮기려면 위 원판들을 방향 규칙에 맞게 먼저 비워야 합니다.

단계별 풀이

1. 작은 원판들을 규칙에 맞게 임시로 치웁니다.
2. 목표 방향이 허용될 때만 큰 원판을 한 단계 보냅니다.
3. 다시 작은 원판들을 목표 상태로 쌓습니다.
4. PDF의 예시 해법은 총 $41$번 이동으로 조건을 만족합니다.

헷갈리기 쉬운 점

일반 하노이의 최적 공식 $2^n-1$을 그대로 쓰면 안 됩니다.

15. 깃발 모으기

문제 한눈에 보기

지정된 깃발을 반드시 포함하면서 A~E 다섯 종류를 모두 담는 최소 연속 구간을 찾는 문제입니다.

답

각 부분 문제에서 PDF 예시와 같은 최소 길이 구간을 고르면 된다.

핵심 개념

고정 점을 포함하는 최단 구간 문제입니다.

왜 이 생각을 먼저 해야 하는지

지정 깃발이 들어가야 하므로, 일반 슬라이딩 윈도우보다 “고정 중심 + 양옆 확장”이 더 자연스럽습니다.

단계별 풀이

1. 지정된 위치를 포함하는 구간에서 시작합니다.
2. 빠진 깃발 종류가 있으면 필요한 쪽으로만 구간을 늘립니다.
3. 다섯 종류가 모두 들어오면, 양끝을 줄일 수 있을 만큼 줄여 최소 길이를 만듭니다.

헷갈리기 쉬운 점

지정 깃발을 빼고 더 짧게 만들 수는 없습니다.

16. 2 등을 찾아라!

문제 한눈에 보기

각 날짜까지의 팔씨름 결과 그래프만 보고, 실력이 2등일 수 있는 학생들을 모두 찾는 문제입니다.

답

PDF의 각 날짜별 회색 정점들이 정답이다.

핵심 개념

2등 후보는 “앞으로 정보를 더 채워도 2등으로 남을 수 있는 사람”입니다.

왜 이 생각을 먼저 해야 하는지

현재 이긴 횟수만 보는 문제가 아니라, 아직 안 한 경기 결과까지 포함해 가능한지 따져야 합니다.

단계별 풀이

1. 각 날짜 그래프에서 가능한 1등 후보를 먼저 생각합니다.
2. 그다음 1등 바로 아래 자리에 올 수 있는 학생을 남깁니다.
3. 다른 학생에게 too many하게 지는 학생은 2등 후보에서 탈락합니다.
4. 이런 기준으로 남는 정점들이 PDF의 회색 정점들입니다.

헷갈리기 쉬운 점

그래프에 간선이 없다고 해서 “졌음”이 아니라 “아직 모름”일 수도 있습니다.

17. 천사와 악마

문제 한눈에 보기

트리 위에서 천사는 출발지에서 최대 6칸, 악마는 최소 3칸 이동했을 때, 가능한 출발지를 모두 찾는 문제입니다.

답

천사 조건을 모두 만족하고, 악마 조건도 모두 피하는 노드들이 정답이다.

핵심 개념

출발지는 “모든 천사로부터 거리 ≤ 6”이면서 “모든 악마로부터 거리 ≥ 3”인 노드입니다.

왜 이 생각을 먼저 해야 하는지

문장을 그대로 거리 조건으로 바꾸면 집합의 교집합 문제로 정리됩니다.

단계별 풀이

1. 각 천사 위치에서 반경 6 이내 노드를 표시합니다.
2. 각 악마 위치에서 반경 2 이내 노드는 출발지가 될 수 없으므로 제외합니다.
3. 남는 노드가 가능한 출발지 전부입니다.

헷갈리기 쉬운 점

악마는 “최소 3칸” 이동했으므로, 거리 0,1,2는 모두 금지입니다.

18. 바둑돌게임

문제 한눈에 보기

돌 38개에서 시작해 2,3,4개 중 하나를 가져가되 직전 수와 같게는 못 가져가는 게임에서 이기는 전략을 찾는 문제입니다.

답

처음에 2개를 가져가고, 이후 losing 상태를 넘기면 된다.

핵심 개념

상태는 (남은 돌 수, 직전 개수)로 잡아야 합니다.

왜 이 생각을 먼저 해야 하는지

같은 수를 연속으로 못 가져가므로, 돌 개수만으로는 승패가 안 정해집니다.

단계별 풀이

1. $win(n,k)$를 표로 채우면 주기 6 패턴이 나타납니다.
2. 시작 상태 $(38,0)$은 winning입니다.
3. 첫 수로 $2$개를 가져가 $(36,2)$를 만들면 상대는 losing 상태를 받습니다.
4. 이후에도 표를 따라 losing 상태만 넘기면 승리합니다.

헷갈리기 쉬운 점

단순한 mod 게임처럼 보여도, 직전 수 때문에 상태가 하나 더 필요합니다.

19. 단조증가수열

문제 한눈에 보기

주어진 수열을 최소 연산으로 단조증가수열로 만드는 문제입니다.

답

$19$번

핵심 개념

이 문제는 수열을 비내림차순으로 만드는 최소 L1 수정 문제입니다.

왜 이 생각을 먼저 해야 하는지

봉우리는 깎고, 골은 올리면서 인접 역전을 합치는 방식으로 보는 것이 자연스럽습니다.

단계별 풀이

1. 왼쪽부터 보며 $A[i]>A[i+1]$인 역전 구간을 찾습니다.
2. 이 구간들을 묶어 적당한 높이로 맞추는 것이 전체 수정량을 줄입니다.
3. 정답 자료의 최적 해에서는 총 연산 수가 $19$입니다.

헷갈리기 쉬운 점

각 칸을 따로따로 고치기보다, 여러 칸을 한 덩어리로 보는 편이 더 유리할 수 있습니다.

20. 삼각형게임

문제 한눈에 보기

13개의 원형 점 사이에 선분을 그어 가며, 먼저 삼각형을 완성하는 사람이 이기는 게임에서 선플레이어 전략을 찾는 문제입니다.

답

PDF의 예시 전략처럼 상대가 같은 점을 다시 쓰게 유도하면 이길 수 있다.

핵심 개념

삼각형은 점 3개가 서로 모두 연결될 때 생기므로, 점 사용 패턴을 강제하는 것이 중요합니다.

왜 이 생각을 먼저 해야 하는지

무작정 좋은 선 하나를 그리기보다, 상대 선택을 제한하는 선이 더 강합니다.

단계별 풀이

1. 먼저 대칭적인 위치에 선을 그어 선택 구조를 만듭니다.
2. 상대가 이미 많이 사용된 점을 다시 고르도록 유도합니다.
3. 그러면 다음 차례에 내가 삼각형을 닫을 기회를 잡을 수 있습니다.

헷갈리기 쉬운 점

내 선만으로 삼각형을 만들 필요는 없습니다. 상대가 그린 선도 같이 써도 됩니다.

개념 한눈에 보기

주제	해당 문제	한 줄 요약
포함배제/확률	1, 2, 4	겹치는 경우를 조심해서 정확히 센다.
재귀/주기	3, 6, 18	규칙을 반복 적용해 값이나 상태 주기를 찾는다.
그래프/트리	7, 11, 16, 17	거리와 후보 집합을 구조적으로 줄여 간다.
논리 추론	8, 10	틀린 정보나 대화 내용도 강한 조건이 된다.
게임 이론	9, 18, 20	losing state를 넘기거나 상대 선택을 강제한다.
DP/최적화	12, 13, 19	상태를 두고 최소 비용이나 경로 수를 누적한다.
구성형	14, 15	조건을 만족하는 한 가지 올바른 절차를 만들면 된다.