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

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

이 문서는 2021 - 초등부 기출문제를 바탕으로, 정답 자료를 초등학생도 따라가기 쉽게 다시 쓴 학습용 풀이 노트입니다. 원본이 정답 PDF이므로, 계산형은 이유를 보강했고 구성형은 공식 예시를 설명형으로 정리했습니다.

1. 사칙연산프로그램

문제 한눈에 보기

입력 $a=4$, $b=2$일 때 첫 번째 출력은 + 또는 -, 두 번째 출력은 ×, ÷, 나머지 중 하나를 써서 나올 수 있는 경우 수를 세는 문제입니다.

답

$6$

핵심 개념

첫 번째 결과와 두 번째 결과를 각각 가능한 값으로 나누어 생각하면 됩니다.

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

연산 이름을 세는 게 아니라 실제 출력값 쌍을 세는 문제이기 때문입니다.

단계별 풀이

1. 첫 번째 결과는 $4+2=6$, $4-2=2$의 두 가지입니다.
2. 두 번째 결과는 $4\times 2=8$, $4÷2=2$, $4\mathrm{mod}2=0$의 세 가지입니다.
3. 따라서 가능한 출력 쌍의 수는 $2\times 3=6$입니다.

헷갈리기 쉬운 점

÷와 mod 결과가 다르다는 점만 놓치지 않으면 됩니다.

2. 쿠키 나눠주기

문제 한눈에 보기

10등이 2개를 받고, 등수가 높아질수록 쿠키를 더 많이 받아야 할 때 최소 총 쿠키 수를 구하는 문제입니다.

답

$65$

핵심 개념

최소가 되려면 차이를 모두 $1$로 두면 됩니다.

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

조금이라도 더 많이 줘야 하므로, 가장 아끼는 방법은 딱 1개씩만 차이 나게 주는 것입니다.

단계별 풀이

1. 10등은 $2$개입니다.
2. 그러면 9등부터 1등까지는 차례로 $3,4,5,\cdots ,11$개를 받습니다.
3. 총합은 $2+3+4+\cdots +11$입니다.
4. 이는 $2$부터 $11$까지의 합이므로 $65$입니다.

헷갈리기 쉬운 점

“더 많아야 한다”는 말은 “같아도 된다”가 아닙니다.

3. 다른 모자 쓰기

문제 한눈에 보기

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

답

$9$

핵심 개념

이 문제는 derangement라고 부르는 대표 경우의 수 문제입니다.

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

전체 $4!$에서 자기 모자를 쓰는 경우를 빼는 방식이 가장 쉽습니다.

단계별 풀이

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$입니다.

헷갈리기 쉬운 점

자기 모자를 쓰는 사람을 뺄 때는 겹쳐서 빠지는 경우를 다시 더해야 합니다.

4. 네자리수

문제 한눈에 보기

어떤 네 자리 수를 9배하면 숫자 순서가 거꾸로 뒤집힌 수가 될 때, 원래 수를 구하는 문제입니다.

답

$1089$

핵심 개념

일의 자리부터 올림을 따라가면 숫자가 거의 고정됩니다.

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

네 자리 수 전체를 다 시험할 필요 없이, 9배의 자리올림 규칙만으로 좁혀집니다.

단계별 풀이

1. 원래 수를 abcd, 뒤집힌 수를 dcba라 합시다.
2. 천의 자리 계산에서 9a에 올림을 더한 값이 한 자리여야 하므로 $a=1$입니다.
3. 그러면 맨 앞자리 $d$는 $9$가 됩니다.
4. 일의 자리에서 $9\times 9=81$이므로 마지막 자리 $a=1$, 올림 $8$이 생깁니다.
5. 이어서 중간 두 자리를 맞추면 $b=0$, $c=8$이 되어 $1089$가 됩니다.
6. 실제로 $1089\times 9=9801$입니다.

헷갈리기 쉬운 점

뒤집힌 수가 네 자리여야 하므로 맨 앞자리 $a$는 0일 수 없습니다.

5. 울타리

문제 한눈에 보기

점선 격자 위 나무들을 직사각형 울타리로 감쌀 때, 둘레가 12인 울타리 안에 넣을 수 있는 최대 나무 수를 묻는 문제입니다.

답

$10$

핵심 개념

둘레가 12이면 가로와 세로 길이 합은 $6$입니다.

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

가능한 직사각형 크기는 많지 않으므로, $1\times 5$, $2\times 4$, $3\times 3$처럼 경우를 줄여서 보면 됩니다.

단계별 풀이

1. 둘레 $12$인 직사각형은 $2(w+h)=12$, 즉 $w+h=6$을 만족합니다.
2. 가능한 크기들을 그림 위에서 옮겨 가며 확인합니다.
3. 가장 잘 들어맞는 위치를 잡으면 나무 $10$그루를 감쌀 수 있습니다.
4. 그보다 많은 경우는 그림에서 나오지 않습니다.

헷갈리기 쉬운 점

울타리는 점선을 따라가야 하므로 기울어진 직사각형은 허용되지 않습니다.

6. 한붓그리기

문제 한눈에 보기

한 번 그은 선을 다시 그리지 않고, 연필을 떼지 않고 그릴 수 없는 그림을 찾는 문제입니다.

답

네 번째 그림

핵심 개념

한붓그리기가 되려면 홀수 차수 정점이 $0$개 또는 $2$개여야 합니다.

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

선 그림은 눈으로만 보면 헷갈리지만, 꼭짓점에서 이어진 선 개수만 세면 바로 판정됩니다.

단계별 풀이

1. 각 보기의 꼭짓점에서 만나는 선 개수를 셉니다.
2. 한붓그리기가 가능한 그림은 홀수 차수 점이 0개 또는 2개입니다.
3. 정답 그림은 홀수 차수 점이 너무 많아 조건을 만족하지 못합니다.
4. 따라서 그릴 수 없는 것은 네 번째 그림입니다.

헷갈리기 쉬운 점

선이 꺾이는 곳만 정점이 아닙니다. 여러 선이 만나는 교점도 정점입니다.

7. 물통

문제 한눈에 보기

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

답

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

핵심 개념

$3$과 $7$의 최대공약수가 $1$이므로 1L를 만들 수 있고, 그러면 나머지도 만들 수 있습니다.

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

1L만 만들 수 있으면, 7L에서 빼거나 3L와 조합해 여러 양을 쉽게 얻을 수 있습니다.

단계별 풀이

1. 7L를 채워 3L로 옮기면 7L 통에 $4$L가 남습니다.
2. 그 $4$L를 3L 통으로 옮기면 7L 통에 $1$L가 남습니다.
3. 3L, 4L, 7L는 이미 만들었습니다.
4. $2\mathrm{L}=3\mathrm{L}-1\mathrm{L}$, $5\mathrm{L}=4\mathrm{L}+1\mathrm{L}$, $6\mathrm{L}=7\mathrm{L}-1\mathrm{L}$처럼 나머지도 만들 수 있습니다.

헷갈리기 쉬운 점

눈금은 없지만, “가득 찰 때까지” 또는 “다 비울 때까지” 옮기면 필요한 양이 자연스럽게 남습니다.

8. 발표순서

문제 한눈에 보기

모든 발표 순서를 알파벳순으로 나열했을 때 CBADEF가 몇 번째인지 구하는 문제입니다.

답

$265$

핵심 개념

앞자리부터 “지금보다 작은 글자로 시작하는 순서가 몇 개 있는지”를 세면 됩니다.

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

720개를 전부 적을 필요 없이, 앞자리 블록 크기만 계산하면 순번이 나옵니다.

단계별 풀이

1. 첫 글자 C보다 작은 A, B로 시작하는 순서가 각각 $5!$개씩 있으므로 $240$개가 먼저 옵니다.
2. C로 시작한 뒤 둘째 글자 B보다 작은 남은 글자 A로 시작하는 경우가 $4!=24$개 있습니다.
3. 그다음 셋째 글자 A는 남은 글자 중 가장 작으므로 더 앞서는 경우는 없습니다.
4. 그래서 순번은 $240+24+1=265$입니다.

헷갈리기 쉬운 점

마지막에 자기 자신까지 포함하므로 $+1$을 꼭 해야 합니다.

9. 2의 100제곱

문제 한눈에 보기

$2^{100}$을 10진수로 썼을 때 10의 자리 숫자를 구하는 문제입니다.

답

$7$

핵심 개념

마지막 두 자리는 주기적으로 반복됩니다.

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

수를 직접 쓰는 것은 너무 크므로, 100으로 나눈 나머지만 보면 충분합니다.

단계별 풀이

1. 우리는 10의 자리만 필요하므로 $2^{100}\mathrm{mod}100$만 알면 됩니다.
2. 계산해 보면 $2^{100}\equiv 76(\mathrm{mod}100)$입니다.
3. 따라서 마지막 두 자리는 $76$이고, 10의 자리는 $7$입니다.

헷갈리기 쉬운 점

일의 자리 주기만 보면 안 됩니다. 10의 자리를 보려면 $\mathrm{mod}100$으로 생각해야 합니다.

10. 과일박스 찾기

문제 한눈에 보기

6개 박스 중 라벨이 정확한 것은 정확히 1개뿐일 때, 그 박스를 알아내기 위해 최악의 경우 몇 개를 열어야 하는지 묻는 문제입니다.

답

$4$

핵심 개념

열어 본 박스가 틀렸는지도 중요한 정보입니다.

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

이 문제는 과일 내용을 다 맞히는 게 아니라 “정확한 라벨 상자 하나”를 찾는 문제입니다.

단계별 풀이

1. 박스 4개를 열어 봅니다.
2. 열어 본 4개 중 라벨과 내용이 같은 상자가 있으면 바로 정답입니다.
3. 만약 4개가 모두 틀렸다면, 남은 2개 중 정확한 라벨은 정확히 1개여야 합니다.
4. 이미 드러난 과일 종류와 남은 라벨을 대조하면 어느 쪽이 맞는지 결정됩니다.
5. 반대로 3개만 열어서는 남은 3개 중 누가 정확한 라벨인지 둘 이상 가능성이 남을 수 있습니다.

헷갈리기 쉬운 점

“틀린 라벨”도 매우 강한 정보입니다. 열어서 안 맞는 순간 가능성이 크게 줄어듭니다.

11. 직소 퍼즐

문제 한눈에 보기

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

답

$14$

핵심 개념

길이 6인 이진 문자열을 회전만 같게 보는 문제와 같습니다.

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

각 변은 “홈” 또는 “돌기” 둘 중 하나라서 경우를 문자열처럼 세면 쉽습니다.

단계별 풀이

1. 아무 제한 없이 세면 $2^6=64$가지입니다.
2. 그런데 회전해서 같아지는 것은 하나로 봅니다.
3. Burnside 보조정리를 쓰면
   $(64+2+4+8+4+2)/6=14$입니다.
4. 따라서 서로 다른 모양은 $14$가지입니다.

헷갈리기 쉬운 점

뒤집기는 허용되지 않으므로 거울대칭은 같은 모양이 아닙니다.

12. 사각형세기

문제 한눈에 보기

그림 안에서 만들 수 있는 모든 사각형 개수를 세는 문제입니다.

답

$30$

핵심 개념

작은 것부터 큰 것까지, 그리고 기울어진 것까지 빠짐없이 분류해야 합니다.

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

눈으로 대충 세면 같은 사각형을 두 번 세거나 큰 사각형을 놓치기 쉽습니다.

단계별 풀이

1. 가장 작은 사각형부터 크기별로 나눠 셉니다.
2. 가로세로가 평행한 사각형과 기울어진 사각형을 따로 보면 중복을 줄일 수 있습니다.
3. 그림 전체를 빠짐없이 세면 총 $30$개입니다.

헷갈리기 쉬운 점

직사각형만이 아니라 모든 사각형입니다.

13. 자리배치하기

문제 한눈에 보기

조건을 만족하도록 A, B, C, D, E 다섯 비버를 다섯 자리에 앉히는 문제입니다.

답

왼쪽부터 B, A, E, D, C

핵심 개념

D는 E의 바로 오른쪽이라는 강한 조건부터 먼저 써야 합니다.

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

붙어 앉는 쌍이 이미 정해져 있으므로, 이 두 자리를 먼저 잡으면 बाकी 조건이 단순해집니다.

단계별 풀이

1. D는 E의 바로 오른쪽이므로 $(E,D)$를 한 덩어리로 봅니다.
2. A나 B는 C 옆 금지, A나 B는 D 옆 금지, B나 C는 E 옆 금지를 차례로 적용합니다.
3. 다섯 자리가 일렬일 때 유일하게 맞는 배치는 B, A, E, D, C입니다.

헷갈리기 쉬운 점

이 문제는 “바로옆”만 금지입니다. 한 칸 떨어져 있으면 괜찮습니다.

14. 2 단계 암호

문제 한눈에 보기

주어진 2단계 암호를 원래 문자열로 복원하는 문제입니다.

답

3MAT4CUPFREE

핵심 개념

암호화의 역순으로, 2단계를 먼저 되돌리고 1단계 치환을 그다음에 되돌리면 됩니다.

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

암호화가 두 번 연속으로 적용되었으므로 복호화는 반대로 해야 합니다.

단계별 풀이

1. 공백을 없애고 2단계 변환부터 거꾸로 풀어 원래 5열 표를 복원합니다.
2. 표를 행 순서대로 읽으면 1단계 변환 문자열이 나옵니다.
3. 이를 두 글자씩 끊어 표에서 역으로 찾으면 원문자가 나옵니다.
4. 끝까지 복원하면 3MAT4CUPFREE입니다.

헷갈리기 쉬운 점

1단계를 먼저 풀려고 하면 안 됩니다. 가장 나중에 한 변환부터 되돌려야 합니다.

15. 스택정렬

문제 한눈에 보기

배열 A의 수를 스택과 배열 B로 옮기며, 제거하기를 최대 한 번 사용해서 최종 B를 오름차순으로 만드는 문제입니다.

답

정답 자료의 클릭 순서를 따르면 된다.

핵심 개념

스택으로 정렬이 안 되는 패턴 하나를 제거해 전체를 스택정렬 가능하게 만드는 문제입니다.

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

스택은 맨 위 원소밖에 못 빼므로, 뒤에서 더 작은 수가 막히는 순간이 생기면 정렬이 깨집니다.

단계별 풀이

1. 넣기와 뽑기만으로는 정렬되지 않는 지점을 찾습니다.
2. 그 지점을 만드는 원소 하나를 제거하기로 없애면 나머지는 스택으로 정렬됩니다.
3. PDF의 예시 클릭 순서대로 진행하면 B가 오름차순이 됩니다.

헷갈리기 쉬운 점

제거하기는 한 번뿐이라, 아무 때나 쓰면 오히려 더 막힐 수 있습니다.

16. 깃발 모으기

문제 한눈에 보기

주어진 깃발을 포함하면서 A, B, C, D, E 다섯 종류를 모두 담는 가장 짧은 연속 구간을 각 부분 문제마다 찾는 문제입니다.

답

PDF의 예시처럼 각 부분 문제에서 최소 길이 구간을 고르면 된다.

핵심 개념

고정된 위치를 반드시 포함하는 “최단 부분배열” 문제입니다.

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

무작정 넓게 잡기보다, 지정 깃발을 포함한 채 양쪽 끝을 최대한 안쪽으로 좁혀야 합니다.

단계별 풀이

1. 지정 깃발을 포함한 상태에서 왼쪽과 오른쪽으로 필요한 종류를 채웁니다.
2. 다섯 종류가 모두 들어오면 끝점을 안쪽으로 더 줄일 수 있는지 확인합니다.
3. 이렇게 찾은 최소 길이 구간이 정답입니다.

헷갈리기 쉬운 점

다섯 종류를 모두 담는 것만으로는 부족하고, 그중에서도 가장 짧아야 합니다.

17. 강건너기

문제 한눈에 보기

몸무게 $3,7,8,9,12,15$인 여섯 사람이 보트로 강을 건널 때 총 비용 최소를 구하는 문제입니다.

답

$62$

핵심 개념

가벼운 두 사람이 셔틀 역할을 하는 고전적인 다리 건너기 전략입니다.

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

무거운 사람을 건널 때마다 누가 보트를 다시 가져오느냐가 총비용을 크게 바꿉니다.

단계별 풀이

1. 가장 무거운 $12,15$를 보내는 데는
   (3,7) 보내기, 3 돌아오기, (12,15) 보내기, 7 돌아오기의 비용 $32$가 유리합니다.
2. 남은 $8,9$도 같은 방식으로 보내면 $23$이 듭니다.
3. 마지막 $3,7$이 건너는 비용은 $7$입니다.
4. 총합은 $32+23+7=62$입니다.

헷갈리기 쉬운 점

항상 가장 가벼운 사람 둘만 보내는 것이 아니라, 누구를 돌아오게 할지가 중요합니다.

18. 2 등을 찾아라!

문제 한눈에 보기

팔씨름 결과 그래프가 주어질 때, 각 날짜까지의 정보만으로 “실력이 2등일 수 있는 학생들”을 모두 찾는 문제입니다.

답

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

핵심 개념

2등 후보는 “누군가에게 지더라도 1등 후보 한 명에게만 질 수 있는 사람”들입니다.

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

2등은 1등에게는 져도 되지만, 3등 이하에게 지는 관계가 강하게 생기면 후보에서 탈락합니다.

단계별 풀이

1. 각 날짜 그래프에서 아직 1등이 될 수 있는 학생을 먼저 봅니다.
2. 그다음 나머지 학생 중, 관계를 더 추가해도 2등이 가능할지 확인합니다.
3. PDF가 색칠한 정점들이 각 날짜의 가능한 2등 후보 전부입니다.

헷갈리기 쉬운 점

현재 2등처럼 보여도, 아직 안 한 경기 결과에 따라 순서가 바뀔 수 있습니다.

19. 바둑돌게임

문제 한눈에 보기

돌 38개에서 시작해 한 번에 2, 3, 4개를 가져가되, 바로 전 사람이 가져간 수와 같은 개수는 못 가져가는 게임입니다.

답

첫 수로 2개를 가져가고, 이후 losing 상태를 유지하면 이길 수 있다.

핵심 개념

상태를 $win(n,k)$로 두면 $n$이 커질수록 주기적으로 반복됩니다.

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

직관으로 두기 어려운 게임이라, “이 상태가 이기는 상태인가?”를 표로 보는 게 가장 확실합니다.

단계별 풀이

1. $win(n,k)$를 “돌 $n$개가 남고 직전에 상대가 $k$개를 가져갔을 때 이길 수 있는가”라고 둡니다.
2. 표를 채워 보면 시작 상태 $(38,0)$은 winning입니다.
3. 그 이유는 첫 수로 $2$개를 가져가 $(36,2)$를 상대에게 넘길 수 있기 때문입니다.
4. $(36,2)$는 losing 상태라, 이후에도 표를 따라 losing 상태를 계속 넘기면 이깁니다.

헷갈리기 쉬운 점

남은 돌 개수만 보는 게임이 아닙니다. 직전에 몇 개를 가져갔는지도 상태에 꼭 들어갑니다.

20. 가위바위보

문제 한눈에 보기

철수와 영희가 정해진 횟수만큼 가위, 바위, 보를 내야 할 때, 철수의 승수를 최대와 최소로 만드는 문제입니다.

답

최대 11번, 최소 2번

핵심 개념

최대는 “이기는 매치”를 최대한 많이 만들고, 최소는 “안 이기는 매치”를 최대한 많이 만드는 문제입니다.

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

각 손모양 개수가 정해져 있어서, 한 쪽 매치를 많이 쓰면 다른 매치가 줄어듭니다.

단계별 풀이

1. 철수의 최대 승수는
   철수 가위 vs 영희 보, 철수 바위 vs 영희 가위, 철수 보 vs 영희 바위를 최대한 맞추면 됩니다.
2. 그래서 $\min (7,7)+\min (3,2)+\min (2,3)=7+2+2=11$입니다.
3. 최소 승수는 영희가 철수의 승리를 최대한 막으면 됩니다.
4. 철수 가위 7번 중 영희가 이를 막을 수 있는 손은 가위 2번과 바위 3번뿐이라서 최대 5번만 막을 수 있습니다.
5. 따라서 적어도 2번은 철수 가위가 영희 보를 만나 철수가 이깁니다.
6. 실제로 그렇게 배치가 가능하므로 최소 승수는 $2$입니다.

헷갈리기 쉬운 점

최소 승수는 “영희의 최대 승수”가 아닙니다. 무승부도 같이 고려해야 합니다.

개념 한눈에 보기

주제	해당 문제	한 줄 요약
경우의 수	1, 3, 8	가능한 결과를 직접 나누거나 순번 블록으로 계산한다.
수와 식	2, 4, 9	등차수열 합, 자리올림, 나머지 주기를 이용한다.
물통/보트	7, 17	상태를 바꾸는 기본 동작을 잘 조합하면 정답이 나온다.
그래프/오일러	6, 18	홀수 차수와 가능한 순위 관계를 보면 된다.
그림 세기	5, 11, 12	가능한 모양을 크기별, 회전별로 빠짐없이 센다.
논리/암호	10, 14	틀린 정보도 정보이고, 복호화는 역순으로 해야 한다.
구성형	13, 15, 16	조건을 만족하는 한 가지 최적 배치를 찾으면 된다.
게임 전략	19, 20	winning/losing 상태와 자원 배치를 보면 최적이 나온다.