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

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

이 문서는 2020 - 고등부 기출문제를 바탕으로, 고등부 1교시 정답 자료를 학습용 풀이 노트로 정리한 것입니다. 계산형은 풀이 논리를 덧붙였고, 비버챌린지형 문제는 공식 정답 화면과 핵심 전략을 함께 적었습니다.

1. 가위바위보 확률

문제 한눈에 보기

5판 3선승제에서 현재 A가 1승 0패이고, 한 판 이길 확률이 $1/2$일 때 A의 최종 승리 확률을 구합니다.

답

$11/16$

핵심 개념

A가 몇 판 만에 우승하는지를 기준으로 경우를 나누면 됩니다.

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

한 번 우승이 확정되면 게임이 즉시 끝나므로, 단순히 4판을 모두 보는 문제와 다릅니다.

단계별 풀이

1. A는 앞으로 2승만 더 하면 됩니다.
2. 2판 만에 이길 확률은 $1/4$입니다.
3. 3판 만에 이길 확률은 $2/8=1/4$입니다.
4. 4판 만에 이길 확률은 $3/16$입니다.
5. 합치면 $1/4+1/4+3/16=11/16$입니다.

헷갈리기 쉬운 점

이미 승부가 난 뒤의 경우를 계속 세면 확률이 커집니다.

2. 지뢰찾기

문제 한눈에 보기

숫자 칸 조건을 모두 만족할 때 가~마 중 반드시 지뢰인 칸을 찾는 문제입니다.

답

가

핵심 개념

지뢰찾기는 숫자 칸을 식으로 읽어 강제되는 칸을 찾는 논리 문제입니다.

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

여러 후보를 막연히 비교하기보다 $0$, $1$, $3$, $5$처럼 강한 정보부터 적용해야 합니다.

단계별 풀이

1. $0$이 적힌 칸 주변은 모두 안전 칸입니다.
2. 윗줄과 오른쪽의 $1$을 함께 보면 윗부분 후보가 거의 한 칸으로 좁혀집니다.
3. 가운데 $3$들, 아래 $5$, 오른쪽 아래 $3$을 차례로 만족시키면 가는 반드시 지뢰여야 합니다.

헷갈리기 쉬운 점

가능한 지뢰와 반드시 지뢰를 혼동하면 안 됩니다.

3. 버블 정렬 3회

문제 한눈에 보기

버블 정렬 한 단계를 세 번 수행한 뒤, 오른쪽에서 세 번째 값을 구하는 문제입니다.

답

$11$

핵심 개념

버블 정렬 한 번마다 가장 큰 값 하나가 맨 뒤로 확정됩니다.

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

전체 정렬을 끝낼 필요 없이, 세 번 뒤의 오른쪽 끝 근처만 추적하면 되기 때문입니다.

단계별 풀이

1. 1회 수행 뒤 $15$가 맨 뒤로 갑니다.
2. 2회 수행 뒤 $12$가 뒤에서 두 번째에 고정됩니다.
3. 3회 수행 뒤 $11$이 뒤에서 세 번째 자리에 옵니다.

헷갈리기 쉬운 점

버블 정렬의 “세 번”은 교환 세 번이 아니라 전체 패스 세 번입니다.

4. 금화 상자

문제 한눈에 보기

세 문장 중 정확히 하나만 참일 때 금화가 들어 있을 수 있는 상자를 찾는 문제입니다.

답

$2$번

핵심 개념

가능한 세 위치를 직접 넣어 참거짓 개수를 세면 됩니다.

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

경우 수가 3개뿐이라 대입 검사가 가장 빠릅니다.

단계별 풀이

1. 금화가 1번이면 참이 2개입니다.
2. 금화가 2번이면 참이 정확히 1개입니다.
3. 금화가 3번이면 참이 2개입니다.
4. 따라서 정답은 2번입니다.

헷갈리기 쉬운 점

“하나만 참”이라는 말을 끝까지 유지해야 합니다.

5. 더 큰 수 확률

문제 한눈에 보기

두 사람이 1부터 20까지 자연수 중 하나를 균등하게 고를 때 $A>B$일 확률을 구합니다.

답

$19/40$

핵심 개념

대칭성과 동률 경우 수를 이용하면 바로 계산됩니다.

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

400가지를 직접 셀 필요 없이, 같은 수를 고르는 경우만 빼면 나머지는 반반이기 때문입니다.

단계별 풀이

1. 전체 경우는 $400$가지입니다.
2. $A=B$는 $20$가지입니다.
3. 남은 $380$가지는 $A>B$, $A<B$가 절반씩입니다.
4. 따라서 $A>B$ 확률은 $190/400=19/40$입니다.

헷갈리기 쉬운 점

동률 때문에 확률이 $1/2$보다 조금 작아집니다.

6. 재혼 가정의 자녀 수

문제 한눈에 보기

전체 자녀 수와 부모와의 유전적 연결 수를 이용해 재혼 후 태어난 자녀 수를 구하는 문제입니다.

답

$6$

핵심 개념

남편 쪽, 부인 쪽, 둘 다인 자녀 수를 변수로 두면 바로 연립식이 나옵니다.

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

긴 서술을 세 부류의 자녀 수 문제로 바꾸면 식 세 개로 정리됩니다.

단계별 풀이

1. 남편이 데려온 자녀를 $x$, 부인이 데려온 자녀를 $y$, 재혼 후 자녀를 $z$라 둡니다.
2. $x+y+z=12$, $x+z=9$, $y+z=9$입니다.
3. 이를 풀면 $z=6$입니다.

헷갈리기 쉬운 점

재혼 후 자녀는 양쪽 모두와 연결되어 두 번 등장합니다.

7. 100개의 문

문제 한눈에 보기

문 번호의 약수만큼 열고 닫는 작업을 했을 때 상태가 다른 문을 찾는 문제입니다.

답

$49$

핵심 개념

완전제곱수만 약수 개수가 홀수라 마지막 상태가 다릅니다.

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

100명의 작업을 실제로 따라가는 것보다 약수 개수로 보는 편이 훨씬 빠릅니다.

단계별 풀이

1. 문 $n$은 $n$의 약수마다 한 번씩 토글됩니다.
2. 약수는 보통 짝지어지지만, 완전제곱수는 가운데 약수 하나가 홀로 남습니다.
3. 보기 중 완전제곱수는 $49$뿐이므로 상태가 다른 문은 $49$입니다.

헷갈리기 쉬운 점

상태가 다르다는 말은 나머지와 반대라는 뜻입니다. 여기서는 $49$만 열려 있습니다.

8. 1, 2, 3 합 분해

문제 한눈에 보기

8을 $1,2,3$의 합으로 나타내는 순서 있는 방법 수를 구하는 문제입니다.

답

$81$

핵심 개념

마지막 수가 $1,2,3$인 경우로 나누면 점화식이 생깁니다.

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

작은 값 결과를 쌓아 올리면 큰 값도 바로 구할 수 있기 때문입니다.

단계별 풀이

1. $f(n)=f(n-1)+f(n-2)+f(n-3)$입니다.
2. $f(1)=1$, $f(2)=2$, $f(3)=4$입니다.
3. 차례로 계산하면 $f(8)=81$입니다.

헷갈리기 쉬운 점

순서를 다르게 쓰면 다른 경우입니다.

9. 동전 거스름돈

문제 한눈에 보기

$5$, $7$, $11$원 동전으로 정확히 만들 수 있는 금액이 언제부터 모두 가능해지는지 구하는 문제입니다.

답

$14$

핵심 개념

연속된 충분한 개수의 금액을 만들 수 있으면, 가장 작은 동전을 더해 그 이후도 모두 만들 수 있습니다.

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

모든 금액을 하나씩 볼 수 없으므로, 어디서부터 패턴이 끊기지 않는지 찾는 게 중요합니다.

단계별 풀이

1. $14,15,16,17,18$은 각각 $7+7$, $5+5+5$, $11+5$, $5+5+7$, $11+7$로 만들 수 있습니다.
2. 이후 금액은 이 다섯 값에 $5$를 더해 계속 만들 수 있습니다.
3. 따라서 $14$ 이상이면 모두 가능합니다.

헷갈리기 쉬운 점

$13$은 만들 수 없으므로 시작점은 14입니다.

10. 2×10 타일 채우기

문제 한눈에 보기

$1\times 2$ 타일로 $2\times 10$ 바닥을 채우는 방법 수를 구합니다.

답

$89$

핵심 개념

왼쪽 첫 칸을 세로로 채우는 경우와 가로 두 장으로 채우는 경우로 분할합니다.

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

첫 열 배치가 정해지면 나머지는 같은 형태의 작은 문제로 줄어들기 때문입니다.

단계별 풀이

1. $g(n)=g(n-1)+g(n-2)$입니다.
2. $g(1)=1$, $g(2)=2$입니다.
3. 계산하면 $g(10)=89$입니다.

헷갈리기 쉬운 점

가로 타일 두 장은 항상 같이 들어가야 합니다.

11. 문자열 사전순

문제 한눈에 보기

조건을 만족하는 길이 10 문자열들을 사전순으로 나열했을 때 22번째를 찾는 문제입니다.

답

aaaabbbbbb

핵심 개념

접두사별 가능한 문자열 수를 세며 22번째가 어느 구간에 들어가는지 찾습니다.

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

문자열 전부를 늘어놓지 않고도 앞자리부터 하나씩 확정할 수 있기 때문입니다.

단계별 풀이

1. aaaaa로 시작하는 문자열은 $21$개입니다.
2. 따라서 22번째 문자열은 aaaaa...가 아니라 aaaab...로 시작합니다.
3. 이후에는 가능한 가장 앞선 문자를 계속 택하면 aaaabbbbbb가 됩니다.

헷갈리기 쉬운 점

$c$ 뒤에는 $c$만 올 수 있다는 조건을 끝까지 적용해야 합니다.

12. 두 돌무더기 게임

문제 한눈에 보기

서로 다른 크기의 두 돌무더기에서 한 번에 한 무더기만 골라 원하는 만큼 가져가고, 마지막 돌을 가져가는 사람이 이기는 게임입니다.

답

항상 A 승리

핵심 개념

두 무더기 님게임의 패배 상태는 두 무더기 크기가 같을 때뿐입니다.

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

문제에서 처음부터 $n\ne m$이라고 했으므로, A가 바로 같은 상태로 만들 수 있습니다.

단계별 풀이

1. 같은 크기 두 무더기는 상대가 무엇을 하든 맞춰서 따라 할 수 있는 패배 상태입니다.
2. 현재는 두 무더기 크기가 다르므로, A는 더 큰 쪽에서 돌을 빼 두 무더기를 같게 만들 수 있습니다.
3. 그러면 B에게 패배 상태를 넘기게 되므로 A가 이깁니다.

헷갈리기 쉬운 점

마지막 돌을 가져가는 사람이 이기는 정상형 게임이라는 점을 놓치면 결론이 바뀝니다.

13. 창고 재배치

문제 한눈에 보기

5개 창고 순환 배치와 6개 창고 순환 배치에서 같은 창고를 계속 쓰는 고객 수를 구하는 문제입니다.

답

$14$

핵심 개념

고객 번호를 $5$와 $6$으로 나눈 나머지가 같아야 합니다.

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

패턴이 $30$명마다 반복되므로, 전체 64명을 직접 세는 것보다 나머지 구조를 보는 편이 정확합니다.

단계별 풀이

1. 옛 창고 번호는 $((n-1)\mathrm{mod}5)+1$, 새 창고 번호는 $((n-1)\mathrm{mod}6)+1$입니다.
2. 두 값이 같으려면 $n-1$의 나머지가 $0,1,2,3,4$ 중 하나로 두 모듈러에서 동시에 같아야 합니다.
3. 30명당 5명씩 일치하고, 64명은 $30+30+4$명이므로 총 $14$명입니다.

헷갈리기 쉬운 점

새 창고 6번은 옛 체계에 없으므로 일치할 수 없습니다.

14. 동전 가져가기 게임

문제 한눈에 보기

세 그룹 $A=3$, $B=3$, $C=4$의 동전에서 한 번에 한 개 또는 한 그룹 전체를 가져가고, 마지막으로 가져가는 사람이 지는 게임입니다.

답

처음에 C에서 1개를 가져가 (3, 3, 3)을 만들면 이길 수 있다.

핵심 개념

이 게임은 정상형 님게임이 아니라 미제르형이라서, 패배 상태를 따로 찾아 상대에게 넘겨야 합니다.

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

대칭처럼 보여도 마지막 동전을 가져가면 지기 때문에, 보통의 “많이 없애기” 전략이 통하지 않습니다.

단계별 풀이

1. 시작 상태 $(3,3,4)$를 한 수만에 $(3,3,3)$으로 만들 수 있습니다.
2. $(3,3,3)$은 다음 차례 사람에게 불리한 패배 상태입니다.
3. 이후에는 상대가 만든 상태를 다시 패배 상태로 되돌리는 식으로 대응하면 선공이 이길 수 있습니다.

헷갈리기 쉬운 점

마지막 동전을 가져가면 이기는 것이 아니라 지므로, 상태 판정이 일반 님게임과 다릅니다.

15. 하노이 탑 모양 바꾸기

문제 한눈에 보기

세 막대의 원판 배치를 주어진 목표 상태와 같게 만드는 문제입니다. 최소 횟수 조건은 없습니다.

답

공식 화면의 목표 배치처럼 만들면 된다.

핵심 개념

큰 원판을 목표 위치에 놓기 위해 작은 원판을 잠시 치우는 하노이 탑 전략을 쓰면 됩니다.

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

큰 원판은 작은 원판 위에 올 수 없으므로, 결국 큰 원판의 이동 순서를 먼저 정해야 합니다.

단계별 풀이

1. 목표 상태에서 가장 큰 원판이 가야 할 막대를 먼저 봅니다.
2. 그 위를 막는 작은 원판들을 다른 막대로 옮깁니다.
3. 큰 원판을 옮긴 뒤, 남은 작은 원판들을 같은 방식으로 재배치합니다.

헷갈리기 쉬운 점

정답 조건은 최소 횟수가 아니라 목표 모양 완성입니다.

16. 선물 경로 최대화

문제 한눈에 보기

두 사람이 서로 다른 방향에서 내려오며 선물을 모을 때, 경로가 최대 한 칸만 겹치도록 하면서 총합을 최대화하는 문제입니다.

답

$137(A=65,B=72)$

핵심 개념

두 경로의 최댓값을 동시에 다루는 대표적인 격자 DP 문제입니다.

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

한 사람만 최적으로 보내면 다른 사람 경로가 막히므로, 교차 구조를 함께 봐야 합니다.

단계별 풀이

1. 네 방향에서 각 칸까지의 최댓값을 미리 계산합니다.
2. 두 경로가 만나는 칸과 만나지 않는 칸의 형태를 나누어 비교합니다.
3. 공식 정답 화면의 최적 총합은 $137$이며, $A=65$, $B=72$입니다.

헷갈리기 쉬운 점

두 사람이 같은 칸을 여러 번 공유할 수 없습니다. 최대 한 칸만 겹칠 수 있습니다.

17. 로봇 자동차 주차

문제 한눈에 보기

다른 자동차를 조금씩 움직여 빨간 자동차를 출구로 빼내는 데 필요한 최소 명령 수를 구하는 문제입니다.

답

$11$

핵심 개념

빨간 차의 최단 이동 수와 방해 차량 제거 수를 합쳐야 전체 최솟값이 나옵니다.

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

길만 짧다고 되는 것이 아니라, 그 길을 비우는 비용까지 포함해야 하기 때문입니다.

단계별 풀이

1. 공식 설명에 따르면 빨간 자동차가 초록 경로를 따라 가는 데 $8$개의 명령이 필요합니다.
2. 이 경로를 확보하려면 다른 자동차 3대를 각각 한 칸씩 움직여야 합니다.
3. 따라서 전체 최소 명령 수는 $8+3=11$입니다.

헷갈리기 쉬운 점

빨간 차 명령 수만 세면 오답입니다. 막고 있는 차를 치우는 명령도 포함됩니다.

18. 트리 영역 게임

문제 한눈에 보기

트리 정점을 번갈아 고르며, 내가 고른 정점들로 이루어진 연결 영역 수 A와 컴퓨터 쪽 영역 수 B의 차 A-B를 최대화하는 문제입니다.

답

최적값은 2이고, 매번 남아 있는 정점 가운데 차수가 가장 작은 정점을 고르면 된다.

핵심 개념

차수가 작은 정점을 먼저 고르면 내 영역을 많이 쪼개지 않고, 상대가 큰 영역을 만들 기회를 줄일 수 있습니다.

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

트리에서는 정점 하나의 차수가 이후 영역 개수에 직접 영향을 주기 때문에, 차수 전략이 곧 게임 전략이 됩니다.

단계별 풀이

1. 잎 정점이나 차수가 작은 정점은 지워도 내 쪽 영역 구조를 크게 망가뜨리지 않습니다.
2. 반대로 차수가 큰 정점을 쉽게 넘겨주면 상대가 큰 연결 영역을 만들기 쉬워집니다.
3. 공식 정답 설명처럼 매 턴 남아 있는 정점 중 차수가 가장 작은 정점을 고르면 최적값 $A-B=2$를 얻을 수 있습니다.

헷갈리기 쉬운 점

내 영역 수만 늘리면 되는 것이 아니라, 동시에 상대 영역 수를 줄여야 합니다.

19. 숨은 순열 찾기

문제 한눈에 보기

길이 15의 숨은 순열을, 교환할 때마다 알려 주는 차이합을 이용해 복원하는 문제입니다.

답

6 4 5 9 3 15 12 13 2 10 1 11 14 8 7

핵심 개념

교환에 따른 총 오차 변화량은 바뀐 두 위치의 실제 값 차이를 거의 직접 보여 줍니다.

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

순열을 직접 볼 수 없더라도, 변화량을 잘 비교하면 위치별 값을 하나씩 고정할 수 있습니다.

단계별 풀이

1. 시작 순열을 정하고 서로 다른 두 칸을 바꿔 봅니다.
2. 차이의 합이 얼마나 늘고 줄었는지 보고, 그 두 칸에 올 수 있는 실제 값 후보를 좁힙니다.
3. 이런 비교를 반복하면 전체 순열을 완전히 복원할 수 있습니다.
4. 공식 정답 화면의 순열은 6 4 5 9 3 15 12 13 2 10 1 11 14 8 7입니다.

헷갈리기 쉬운 점

한 번의 교환은 두 칸에 대한 정보만 준다는 점을 끝까지 이용해야 합니다.

20. 트리 변환 최소 연산

문제 한눈에 보기

왼쪽 트리에서 간선 하나를 지우고 다른 간선 하나를 추가하는 연산만으로 오른쪽 트리와 같게 만들 때 최소 연산 수를 구하는 문제입니다.

답

$19$

핵심 개념

한 번의 연산은 “불필요한 간선 하나 제거 + 필요한 간선 하나 추가”를 동시에 처리합니다.

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

최소 연산 수는 결국 두 트리가 공통으로 갖는 간선을 최대한 남기는 문제로 바뀌기 때문입니다.

단계별 풀이

1. 현재 트리와 목표 트리에서 같은 간선은 그대로 두는 것이 가장 이득입니다.
2. 공통이 아닌 간선은 한 번의 연산으로 하나씩 바로잡을 수 있습니다.
3. 공식 정답 자료에서 필요한 최소 연산 수는 $19$입니다.

헷갈리기 쉬운 점

간선을 아무 데나 추가하면 사이클이 생겨 트리가 아니게 되므로, 제거와 추가를 항상 함께 생각해야 합니다.

개념 한눈에 보기

주제	해당 문제	한 줄 요약
확률과 경우의 수	1, 5	종료 시점과 대칭 구조를 잡으면 계산이 짧아진다.
논리와 수식화	2, 4, 6	보드 숫자, 참거짓, 가족 관계를 식으로 바꾸면 답이 고정된다.
점화식과 DP	8, 10, 16	마지막 선택이나 경로 방향으로 쪼개면 큰 문제를 작은 문제로 줄일 수 있다.
나머지와 수론	7, 9, 13	약수 개수와 나머지 반복 패턴을 이용하면 직접 세지 않아도 된다.
게임 이론	12, 14, 18	상대에게 패배 상태를 넘기거나, 구조상 유리한 정점을 선점하는 것이 핵심이다.
구성형	15, 17, 19, 20	정답 배치 하나를 찾되, 왜 최소인지 또는 왜 복원이 가능한지까지 설명해야 한다.