3 - 2021 KOI 1교시 고등부 풀이 정리

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

이 문서는 2021 - 고등부 기출문제를 바탕으로, 고등학생 기준에서 다시 읽기 쉽게 정리한 학습용 풀이 노트입니다. 원본이 정답 PDF이므로, 계산형은 핵심 논리를 압축해 적었고 구성형은 공식 예시가 왜 통하는지 중심으로 설명했습니다.

1. 상금배분

문제 한눈에 보기

7전 4선승제에서 A가 2승으로 앞선 시점에, 남은 우승 확률에 비례해 16억원을 나누는 문제입니다.

답

$13$억원

핵심 개념

A의 우승 확률은 상태 (A 2승, B 0승)에서의 시리즈 승률입니다.

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

공정 배분은 “현재까지 몇 경기 이겼는가”가 아니라 “앞으로 우승할 확률”에 비례해야 합니다.

단계별 풀이

1. B가 우승하려면 A가 2승 하기 전에 먼저 4승해야 합니다.
2. 가능한 경우는 BBBB 또는 길이 5에서 A가 한 번만 끼는 ABBBB, BABBB, BBABB, BBBAB입니다.
3. 따라서
   $P(B\text{ 우승})=1/16+4/32=3/16$
4. $P(A\text{ 우승})=13/16$이므로 A 몫은 $16\times 13/16=13$억원입니다.

헷갈리기 쉬운 점

5경기를 끝까지 다 치른다고 가정하면 안 됩니다. 시리즈는 중간에 종료됩니다.

2. 구슬경로의수

문제 한눈에 보기

통로 안에서 아래로만 움직이는 구슬이 지날 수 있는 서로 다른 경로 수를 세는 문제입니다.

답

$35$

핵심 개념

각 갈림점까지 오는 경로 수를 누적하는 DAG DP입니다.

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

같은 중간 지점으로 여러 경로가 합쳐지므로, 완전탐색보다 경로 수 누적이 적절합니다.

단계별 풀이

1. 입구에서 시작해 각 분기점으로 들어오는 경로 수를 적습니다.
2. 한 분기점의 경로 수는 바로 위에서 들어오는 경로 수들의 합입니다.
3. 그림의 모든 합류 지점에 이 규칙을 적용하면 최종 출구 경로 수가 $35$가 됩니다.

헷갈리기 쉬운 점

같은 모양의 부분 경로라도 시작 지점이 다르면 다른 경로입니다.

3. 동전과확률

문제 한눈에 보기

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

답

$6$

핵심 개념

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

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

동전 두 개를 한 번에 뽑으므로 조합으로 세는 것이 가장 자연스럽습니다.

단계별 풀이

1. 전체 경우는 $C(10,2)=45$.
2. 유리한 경우는 $C(x,2)$.
3. 따라서 $C(x,2)/45\le 0.4$, 즉 $x(x-1)/2\le 18$.
4. $x=6$은 가능, $x=7$은 불가능하므로 최대는 $6$입니다.

헷갈리기 쉬운 점

순서 있는 경우가 아니라 조합입니다.

4. 발표순서

문제 한눈에 보기

알파벳 순으로 정렬된 모든 발표 순서 중 CBADEF가 몇 번째인지 구하는 문제입니다.

답

$265$

핵심 개념

순열의 사전식 순번은 factoradic 방식으로 구할 수 있습니다.

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

720개를 직접 나열할 필요 없이, 앞자리 블록 크기만 계산하면 됩니다.

단계별 풀이

1. 첫 글자 C보다 작은 A,B로 시작하는 순열이 $2\times 5!=240$개 있습니다.
2. 그다음 C로 시작하면서 둘째 글자가 B보다 작은 A인 경우가 $4!=24$개 있습니다.
3. 이후는 더 앞서는 경우가 없습니다.
4. 따라서 순번은 $240+24+1=265$입니다.

헷갈리기 쉬운 점

마지막 $+1$은 자기 자신 순번을 포함하기 위한 것입니다.

5. 돌 무더기게임

문제 한눈에 보기

세 돌무더기 $1,2,3$에서 시작하는 정상 Nim의 승패를 묻는 문제입니다.

답

B가 항상 승리한다.

핵심 개념

초기 님합이 $0$이면 선플레이어가 집니다.

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

Nim은 님합 하나로 승패가 판정되는 대표 게임입니다.

단계별 풀이

1. 시작 님합은 $1\mathrm{xor}2\mathrm{xor}3=0$입니다.
2. 님합 0은 losing position입니다.
3. A가 어떤 수를 가져가도 님합이 0이 아닌 상태가 됩니다.
4. B는 다시 님합 0으로 돌려놓을 수 있으므로 결국 승리합니다.

헷갈리기 쉬운 점

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

6. 직소퍼즐

문제 한눈에 보기

육각형 퍼즐 조각의 6변에 홈/돌기가 있을 때, 회전만 같게 보아 서로 다른 모양의 수를 묻는 문제입니다.

답

$14$

핵심 개념

길이 6의 이진 목걸이(necklace) 개수 문제입니다.

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

변마다 두 상태뿐이므로, 회전 동치만 처리하면 됩니다.

단계별 풀이

1. 회전을 무시하지 않으면 $2^6=64$가지입니다.
2. Burnside 보조정리를 적용합니다.
3. 회전 0칸은 $64$, 1·5칸은 $2$, 2·4칸은 $4$, 3칸은 $8$개를 고정합니다.
4. 따라서
   $(64+2+4+8+4+2)/6=14$입니다.

헷갈리기 쉬운 점

뒤집기는 허용되지 않으므로 dihedral이 아니라 cyclic rotation만 봅니다.

7. 삼각형위의격자점

문제 한눈에 보기

삼각형 ABC의 둘레 위에 있는 격자점 개수를 묻는 문제입니다.

답

$42$

핵심 개념

두 격자점을 잇는 선분 위 격자점 수는 $\gcd (|dx|,|dy|)$로 셀 수 있습니다.

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

둘레 전체를 직접 세기보다, 각 변의 격자점 개수를 합하면 됩니다.

단계별 풀이

1. AB에서 차이는 $(155,29)$이므로 $\gcd =1$.
2. BC에서 차이는 $(210,150)$이므로 $\gcd =30$.
3. CA에서 차이는 $(55,121)$이므로 $\gcd =11$.
4. 다각형 둘레 격자점 수는 이 gcd들의 합이므로 $1+30+11=42$입니다.

헷갈리기 쉬운 점

각 변마다 $+1$을 하면 꼭짓점을 중복해서 세게 됩니다.

8. 숫자 추측

문제 한눈에 보기

두 번 던진 정사면체의 바닥 숫자 $a\le b$에 대해, 합과 곱을 들은 두 사람이 대화한 뒤 $a^2+b^2$를 구하는 문제입니다.

답

$17$

핵심 개념

대화에 따라 가능한 후보 쌍을 차례로 제거하는 논리 퍼즐입니다.

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

합과 곱만으로는 모호하지만, “알 수 있는가/없는가” 발언이 후보를 강하게 줄입니다.

단계별 풀이

1. 가능한 $(a,b)$를 $1\le a\le b\le 4$에서 모두 적습니다.
2. “곱만 듣고는 모르겠다”에서 곱이 유일한 경우를 제거합니다.
3. “합을 듣고 이제는 안다”에서 남은 후보 중 합이 하나뿐인 경우만 남깁니다.
4. “합과 곱이 다르다”까지 반영하면 $(1,4)$만 남습니다.
5. 따라서 $a^2+b^2=1^2+4^2=17$입니다.

헷갈리기 쉬운 점

매 대화는 이전 대화로 줄어든 후보 집합 위에서 다시 해석해야 합니다.

9. 항아리

문제 한눈에 보기

검은 돌과 흰 돌이 있는 항아리에서 정해진 규칙으로 두 돌을 계속 꺼낼 때, 마지막 남는 돌의 색을 구하는 문제입니다.

답

B, W, W

핵심 개념

흰 돌 개수의 홀짝이 불변량입니다.

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

돌 수는 계속 바뀌지만, 어떤 성질은 끝까지 유지될 수 있습니다. 이 문제는 흰 돌의 홀짝이 바로 그것입니다.

단계별 풀이

1. BB를 꺼내면 흰 돌 개수는 변하지 않습니다.
2. BW를 꺼내도 흰 돌은 다시 들어가므로 흰 돌 개수는 그대로입니다.
3. WW를 꺼내면 흰 돌이 2개 줄어듭니다.
4. 즉 흰 돌 개수의 홀짝은 항상 유지됩니다.
5. 마지막 한 돌이 W가 되려면 처음 흰 돌 수가 홀수, B가 되려면 짝수여야 합니다.
6. 따라서 $jug(10,34)=B$, $jug(45,5)=W$, $jug(100,111)=W$입니다.

헷갈리기 쉬운 점

검은 돌 개수는 중요하지 않습니다. 마지막 색을 결정하는 것은 흰 돌 수의 홀짝입니다.

10. 중심 노드 찾기

문제 한눈에 보기

진입 차수 0, 진출 차수 $n-1$인 중심 노드를 찾기 위한 query 최소 횟수를 묻는 문제입니다.

답

$n-1$

핵심 개념

두 후보를 한 번 비교할 때마다 후보 하나를 확실히 탈락시킬 수 있습니다.

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

이 문제는 그래프 문제이면서 동시에 후보 제거 문제입니다.

단계별 풀이

1. $query(a,b)$에서 $a\to b$가 있으면 $b$는 중심이 될 수 없습니다.
2. 간선이 없으면 $a$는 중심이 될 수 없습니다.
3. 즉 query 하나로 후보 하나 제거가 가능합니다.
4. 후보가 $n$개이므로 하나를 남기려면 $n-1$번이 필요하고, 이만큼이면 실제로 가능합니다.

헷갈리기 쉬운 점

후보를 하나로 줄인 뒤에는 중심 노드 존재가 이미 보장되어 있어 추가 검증이 필요 없습니다.

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

문제 한눈에 보기

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

답

$53$

핵심 개념

격자 DP에 “지난 ● 개수” 상태를 더한 문제입니다.

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

조건 없는 경로 수에 비해 상태 하나만 추가하면 그대로 셀 수 있습니다.

단계별 풀이

1. 각 칸에서 $0$개, $1$개, 2개 이상 상태로 오는 경로 수를 따로 둡니다.
2. 왼쪽과 위쪽 값들을 더하며 진행합니다.
3. ● 칸에 도착하면 상태를 올리고, X 칸은 막습니다.
4. 도착점의 2개 이상 상태가 $53$입니다.

헷갈리기 쉬운 점

정확히 2개가 아니라 2개 이상입니다.

12. 사각형세기

문제 한눈에 보기

그림 안의 모든 사각형 개수를 묻는 문제입니다.

답

$30$

핵심 개념

작은 사각형, 큰 사각형, 기울어진 사각형을 분류해 세면 됩니다.

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

이런 그림 세기는 중복 없이 체계적으로 나누는 것이 핵심입니다.

단계별 풀이

1. 가장 작은 사각형들을 먼저 셉니다.
2. 이를 합친 중간 크기와 전체를 덮는 큰 사각형을 셉니다.
3. 축에 평행하지 않은 사각형도 빠뜨리지 않고 더하면 총 $30$개입니다.

헷갈리기 쉬운 점

직사각형만 세는 문제가 아닙니다.

13. 첫 월급

문제 한눈에 보기

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

답

$1375$원

핵심 개념

묶음 단가를 비교하면 3개 묶음이 가장 효율적입니다.

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

묶음 구매 문제는 먼저 단가를 보는 것이 정석입니다.

단계별 풀이

1. 단가는 각각 $175$, $400/3$, $140$원입니다.
2. 가장 싼 것은 3개 묶음입니다.
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$번 이동의 한 가지 정답입니다.

헷갈리기 쉬운 점

일반 하노이의 대칭성이 방향 제한 때문에 깨집니다.

15. 2 등을 찾아라!

문제 한눈에 보기

4일 동안의 팔씨름 결과 그래프가 단계별로 주어질 때, 각 시점에서 2등일 수 있는 학생들을 모두 고르는 문제입니다.

답

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

핵심 개념

2등 후보는 현재 정보와 미래의 가능한 경기 결과를 모두 고려해도 2등이 가능해야 합니다.

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

부분 정보 그래프에서는 간선이 없다는 사실이 “패배”가 아니라 “아직 모름”일 수 있습니다.

단계별 풀이

1. 각 날짜 그래프에서 가능한 1등 후보 집합을 먼저 구합니다.
2. 각 학생이 그 1등 후보 바로 아래에 들어갈 수 있는지 확인합니다.
3. 모순 없이 가능한 학생들만 남기면 PDF의 회색 정점과 일치합니다.

헷갈리기 쉬운 점

현재 들어오는 간선 수만으로 2등 여부를 결정하면 안 됩니다.

16. 천사와 악마

문제 한눈에 보기

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

답

모든 천사와는 거리 6 이하이고, 모든 악마와는 거리 3 이상인 노드들이 정답이다.

핵심 개념

거리 조건의 교집합과 차집합 문제입니다.

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

이동 규칙을 그대로 거리 부등식으로 바꾸면 구조가 아주 단순해집니다.

단계별 풀이

1. 각 천사 노드에서 반경 6 안에 있는 노드들을 표시합니다.
2. 이 표시들의 교집합이 “천사 조건”입니다.
3. 각 악마 노드에서 반경 2 안의 노드를 지웁니다.
4. 남는 노드가 가능한 출발지입니다.

헷갈리기 쉬운 점

악마 조건은 “3 이상”이므로 거리 2까지는 모두 금지입니다.

17. 단조증가수열

문제 한눈에 보기

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

답

$19$번

핵심 개념

이 문제는 L1 isotonic regression의 정수 버전으로 볼 수 있습니다.

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

역전 구간들을 따로 고치기보다 블록으로 합쳐 평균 높이 근처에 맞추는 것이 총 수정량을 줄입니다.

단계별 풀이

1. 인접한 역전 구간들을 묶어 블록으로 봅니다.
2. 블록의 높이를 조정해 전체가 비내림차순이 되게 합니다.
3. 가장 작은 총 수정량은 $19$입니다.

헷갈리기 쉬운 점

각 칸을 독립적으로 바로잡는 탐욕은 최적을 보장하지 않습니다.

18. 삼각형게임

문제 한눈에 보기

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

답

PDF의 예시 전략대로 상대가 이미 많이 쓴 점을 다시 고르게 유도하면 이길 수 있다.

핵심 개념

이 게임은 “선분”보다 “점 사용 구조”를 강제하는 것이 중요합니다.

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

삼각형은 세 점이 모두 연결되는 순간 생기므로, 점을 몰아 쓰게 만드는 편이 유리합니다.

단계별 풀이

1. 대칭적인 위치에 선을 두어 상대의 선택 폭을 줄입니다.
2. 상대가 이미 사용한 점을 다시 쓰도록 압박합니다.
3. 그러면 다음 차례에 내가 삼각형을 닫을 수 있는 구조가 생깁니다.

헷갈리기 쉬운 점

상대가 그은 선도 삼각형 완성에 사용할 수 있습니다.

19. 팀 구성

문제 한눈에 보기

상대가 먼저 고른 팀과 겹치지 않으면서, 내부가 연결된 팀 중 실력 합이 최대가 되도록 각 상황마다 고르는 문제입니다.

답

10개 상황의 최대 합은 차례로 8, 6, 7, 6, 6, 5, 6, 5, 7, 3

핵심 개념

상대가 막은 정점을 제외한 그래프에서, 연결된 부분집합의 최대 가중치 합을 찾는 문제입니다.

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

사람을 많이 고르는 것이 아니라, 연결 조건을 지키며 점수 합이 최대여야 하기 때문입니다.

단계별 풀이

1. 각 상황에서 상대가 차지한 정점을 제거합니다.
2. 남은 그래프에서 연결된 부분집합들만 후보로 봅니다.
3. 각 부분 문제의 최대 합은 PDF가 제시한 대로
   $8,6,7,6,6,5,6,5,7,3$입니다.

헷갈리기 쉬운 점

점수 합이 커도 그래프가 둘로 끊기면 팀이 될 수 없습니다.

20. 2 행정렬

문제 한눈에 보기

위 행은 $\mathrm{1..15}$, 아래 행은 $-\mathrm{1..}-15$가 되도록, 서로 다른 두 행의 한 칸씩을 바꾸는 연산만으로 정렬하는 문제입니다.

답

PDF의 교환 순서대로 하면 조건을 만족하게 정렬된다.

핵심 개념

각 수를 “제자리 열”로 보내는 순환들을 하나씩 분해해 처리하는 문제입니다.

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

임의의 두 칸을 바꿀 수 있지만, 각 쌍은 최대 두 번까지만 가능하므로 순환을 잘 풀어야 합니다.

단계별 풀이

1. 각 양수와 음수가 목표로 가야 할 열을 확인합니다.
2. 잘못 놓인 원소들을 순환으로 묶습니다.
3. PDF의 교환 순서는 이 순환들을 끊어 가며 최종적으로 두 행을 모두 정렬하는 한 가지 구성입니다.

헷갈리기 쉬운 점

한 쌍의 칸을 세 번 이상 바꾸면 규칙 위반입니다.

개념 한눈에 보기

주제	해당 문제	한 줄 요약
확률/경우의 수	1, 3, 4, 8	상태 확률과 사전식 순번, 후보 제거를 함께 쓴다.
경로/그래프 DP	2, 11	DAG에서 경로 수는 누적 합으로 센다.
게임 이론	5, 18	님합이나 강제 구조를 이용해 winning state를 만든다.
군작용/대칭	6	회전 동치가 있으면 Burnside가 정석이다.
격자/수론	7, 9	gcd와 불변량이 정답을 빠르게 결정한다.
후보 제거	10, 15, 16	query나 거리 제약으로 후보를 계속 줄인다.
그림 세기	12	큰 것과 작은 것을 분류해 중복 없이 센다.
최적화	13, 17, 19, 20	단가, 수정량, 연결성, 순환 분해를 함께 본다.