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

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

이 문서는 2019 - 초등부 기출문제를 바탕으로, 초등부 1교시 정답 자료를 학습용 풀이 노트로 다시 정리한 것입니다. 그림형 문제는 공식 정답 화면을 함께 넣었고, 계산형은 핵심 아이디어를 짧게 보강했습니다.

1. 세 수 정렬 비교횟수

문제 한눈에 보기

서로 다른 세 수 $a,b,c$를 비교만 해서 항상 크기순으로 정렬하려면 최소 몇 번 비교해야 하는지 묻는 문제입니다.

답

$3$

핵심 개념

세 수의 순서는 $3!=6$가지라서, 비교 결과만으로 이 6가지를 모두 구분해야 합니다.

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

비교 1번은 경우를 둘로만 나누므로, 몇 번이면 6가지를 구분할 수 있는지 바로 볼 수 있습니다.

단계별 풀이

1. 비교 2번으로 얻을 수 있는 결과 경우 수는 최대 $2^2=4$가지뿐입니다.
2. 하지만 세 수의 가능한 순서는 $6$가지입니다.
3. 따라서 2번 비교만으로는 항상 구분할 수 없습니다.
4. 실제로는 a-b, b-c, 필요하면 a-c를 비교해 3번이면 됩니다.

헷갈리기 쉬운 점

운 좋게 맞히는 경우가 있어도 안 됩니다. 어떤 입력에서도 항상 가능해야 합니다.

2. 친구 인사 시간

문제 한눈에 보기

다섯 명이 모든 쌍과 한 번씩 인사할 때, 한 사람은 한 번에 한 명하고만 인사할 수 있습니다. 전체 최소 시간을 구합니다.

답

$5$분

핵심 개념

사람이 5명이면 한 분 동안 동시에 할 수 있는 인사는 최대 2쌍뿐입니다.

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

전체 인사 횟수와, 1분에 동시에 처리할 수 있는 최대 쌍 수를 비교하면 하한이 바로 나옵니다.

단계별 풀이

1. 다섯 명의 모든 인사쌍 수는 $5C2=10$쌍입니다.
2. 한 번에 동시에 가능한 인사는 최대 2쌍입니다.
3. 따라서 최소 $10÷2=5$분이 필요합니다.
4. 실제로 원형 순서처럼 짜면 5분 만에 모두 끝낼 수 있습니다.

헷갈리기 쉬운 점

사람 수가 홀수라서 매 분마다 반드시 한 명은 쉬게 됩니다.

3. 동심원 칠하기

문제 한눈에 보기

반지름이 서로 다른 원 5개가 있을 때, 원 사이 5개 영역을 흰색 또는 회색으로 칠해 만들 수 있는 서로 다른 그림 수를 구합니다.

답

$32$

핵심 개념

각 영역마다 색 선택이 2가지씩 독립입니다.

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

영역이 5개라는 사실만 알면 곱의 법칙으로 바로 끝납니다.

단계별 풀이

1. 가장 안쪽 원판 포함, 색칠할 영역은 모두 5개입니다.
2. 각 영역은 흰색 또는 회색 두 선택이 있습니다.
3. 따라서 전체 경우 수는 $2^5=32$가지입니다.

헷갈리기 쉬운 점

원 개수가 5개여도 색칠 영역 수도 5개라는 점을 놓치지 않으면 됩니다.

4. 물통 물빼기

문제 한눈에 보기

왼쪽 물통이 12초 걸린다는 정보를 바탕으로, 오른쪽 물통의 물이 완전히 빠지는 시각을 구하는 문제입니다.

답

$18$초

핵심 개념

구멍 위로 연결된 물의 양이 시간과 정확히 대응합니다.

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

초마다 “현재 구멍과 연결된 물 한 칸”씩 빠지므로, 결국 빠지는 총 칸 수를 세는 문제로 바뀝니다.

단계별 풀이

1. 왼쪽 예시가 12초라는 것은, 구멍과 연결된 물 칸이 총 12칸이라는 뜻입니다.
2. 오른쪽 물통도 같은 방식으로 아래에서부터 연결되는 물 칸 수를 차례로 세면 됩니다.
3. 계단처럼 막히는 부분 때문에 한 번에 전부 빠지지 않고, 윗부분 물이 순서대로 내려옵니다.
4. 공식 정답 화면의 결과는 $18$초입니다.

헷갈리기 쉬운 점

그림의 전체 물 칸 수를 세는 게 아니라, 실제로 구멍 쪽으로 흘러갈 수 있는 순서를 세야 합니다.

5. 369 게임

문제 한눈에 보기

$201$부터 $300$까지 말하거나 박수칠 때, 숫자에 $3$, $6$, $9$가 하나라도 있으면 박수를 칩니다. 전체 박수 횟수를 구합니다.

답

$52$

핵심 개념

조건을 만족하는 수의 개수를 세면 됩니다.

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

각 수에서 박수는 많아야 1번이므로, 단순히 “해당 숫자가 몇 개인가”를 세면 끝입니다.

단계별 풀이

1. $201$부터 $300$까지 100개의 수를 봅니다.
2. 이 중 자릿수에 $3$, $6$, $9$가 하나라도 들어 있는 수를 세면 됩니다.
3. 직접 세거나 보수를 쓰면 총 $52$개가 나옵니다.

헷갈리기 쉬운 점

이 문제는 숫자 안에 $3,6,9$가 여러 개 있어도 박수는 한 번만 칩니다.

6. 자 위의 개미

문제 한눈에 보기

30cm 자 위의 5마리 개미가 서로 만나면 방향을 바꾸며 움직일 때, 가장 먼저 떨어진 개미와 가장 늦게 떨어진 개미의 정지 시각 차이를 구합니다.

답

$26$

핵심 개념

같은 속력 개미가 만나 방향을 바꾸는 것은, 사실 서로 통과한 것과 결과가 같습니다.

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

충돌을 일일이 추적하지 않아도, 각 개미의 “끝까지 가는 시간”만 보면 정답을 쉽게 구할 수 있습니다.

단계별 풀이

1. 만남 후 방향을 바꾸는 대신, 개미가 서로 몸만 바꿔치기했다고 생각해도 떨어지는 시각 집합은 같습니다.
2. 그러면 각 출발점에서 왼쪽 끝 또는 오른쪽 끝까지 가는 시간을 바로 읽을 수 있습니다.
3. 자를 완전히 벗어나 바닥에 떨어지는 시간 1도 추가해야 합니다.
4. 공식 정답 화면의 계산 결과, 가장 빠른 것과 가장 늦은 것의 차이는 $26$입니다.

헷갈리기 쉬운 점

끝에 도달한 순간이 아니라, 자를 벗어나 바닥에 떨어져 멈추는 데도 시간 1이 더 걸립니다.

7. 격자판 개미

문제 한눈에 보기

9×9 격자점 위 개미 8마리가 화살표 방향으로 움직이다가 경계, 다른 개미, 이미 지나간 경로를 만나면 멈출 때, 모든 개미가 멈추는 최초 시각을 구합니다.

답

$5$

핵심 개념

먼저 멈추는 개미가 만든 경로가 다음 개미들을 멈추게 하므로, 초기 몇 초를 차례대로 추적하면 됩니다.

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

마지막 시각만 보려 하면 복잡하지만, “몇 초 뒤에 어떤 경로가 생기나”를 보면 연쇄가 짧게 끝납니다.

단계별 풀이

1. 각 개미의 직선 경로를 그려 보고, 서로 직접 만나는 경우를 먼저 찾습니다.
2. 먼저 멈춘 개미들의 출발점과 경로가 새로운 장애물이 됩니다.
3. 이를 1초씩 추적하면 모든 개미가 멈추는 가장 이른 시각이 $5$초임을 알 수 있습니다.

헷갈리기 쉬운 점

다른 개미가 “지나갔던 경로”와 만나도 멈춘다는 조건이 매우 중요합니다.

8. 9글자 회문 개수

문제 한눈에 보기

알파벳 $a,b,c$로 만들 수 있는 길이 9 회문의 개수를 구합니다.

답

$243$

핵심 개념

회문은 앞 절반만 정하면 뒤 절반이 자동으로 정해집니다.

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

9글자 전체를 다 고르는 게 아니라, 가운데 포함 앞 5글자만 고르면 됩니다.

단계별 풀이

1. 길이 9 회문은 $1,2,3,4,5$번째 글자를 정하면 나머지가 자동 결정됩니다.
2. 각 자리마다 선택은 3가지입니다.
3. 따라서 전체 개수는 $3^5=243$입니다.

헷갈리기 쉬운 점

길이가 홀수이므로 가운데 글자도 자유롭게 고를 수 있습니다.

9. 빼기 연산

문제 한눈에 보기

현재 수의 가장 높은 자릿수 숫자를 빼는 연산을 반복할 때, $40$이 $0$이 되기까지 최소 몇 번 필요한지 묻는 문제입니다.

답

$19$

핵심 개념

연산 규칙이 완전히 정해져 있으므로, 실제로 따라가면 됩니다.

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

매번 뺄 수 있는 수가 하나뿐이라서 전략 문제처럼 생각할 필요가 없습니다.

단계별 풀이

1. $40\to 36\to 33\to 30\to 27\to 25\to 23\to 21\to 19$
2. 이어서
   $19\to 18\to 17\to 16\to 15\to 14\to 13\to 12\to 11\to 10\to 9\to 0$
3. 모두 세면 연산 횟수는 $19$번입니다.

헷갈리기 쉬운 점

$40$에서는 $4$를 빼는 것이지 $40$을 빼는 것이 아닙니다.

10. 토끼와 마법의 벨

문제 한눈에 보기

어린 토끼 쌍 1쌍에서 시작해, 벨을 울릴 때마다 어린 토끼는 어른이 되고 어른 토끼는 어린 토끼 한 쌍을 낳습니다. 토끼 쌍이 50쌍 이상이 되는 최소 벨 횟수를 구합니다.

답

$9$

핵심 개념

토끼 수는 피보나치 수열처럼 늘어납니다.

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

이번 단계의 어린 토끼 수가 직전 단계의 어른 토끼 수와 같아서 자연스럽게 점화식이 생깁니다.

단계별 풀이

1. 벨 횟수에 따른 전체 쌍 수를 세면
   $1,2,3,5,8,13,21,34,55,\cdots$처럼 늘어납니다.
2. $34$는 아직 부족하고, 그다음 $55$가 처음으로 50 이상입니다.
3. 따라서 최소 벨 횟수는 $9$번입니다.

헷갈리기 쉬운 점

어린 토끼는 바로 새끼를 낳지 않고, 한 번 벨을 더 울린 뒤 어른이 되어야 낳습니다.

11. 정삼각형으로 만드는 볼록다각형

문제 한눈에 보기

같은 크기의 정삼각형을 변끼리 붙여 속이 꽉 찬 볼록다각형을 만들 때, 만들 수 없는 다각형의 변 개수를 찾는 문제입니다.

답

$7$각형

핵심 개념

정삼각형을 붙여 만든 볼록도형의 외곽 각은 60도 단위로만 생깁니다.

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

가능한 외곽 모양이 많이 제한되므로, 작은 변 개수부터 따져 보면 불가능한 경우가 보입니다.

단계별 풀이

1. $3$각형, $4$각형, $5$각형, $6$각형은 실제로 만들 수 있습니다.
2. 하지만 7변 모두가 정삼각형 격자 방향을 따르면서 볼록하게 닫히는 모양은 만들 수 없습니다.
3. 따라서 만들 수 없는 것은 $7$각형입니다.

헷갈리기 쉬운 점

아무 7각형이 아니라, 정삼각형들을 빈틈 없이 붙인 볼록도형이어야 합니다.

12. 백만 번째 숫자

문제 한눈에 보기

$123456789101112\cdots$처럼 이어 쓸 때 백만 번째 자리에 오는 숫자를 구합니다.

답

$1$

핵심 개념

한 자리 수, 두 자리 수, 세 자리 수가 차지하는 자릿수를 블록으로 끊어 계산합니다.

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

백만 번째까지 직접 쓰는 것은 불가능하므로, 몇 자리 수 구간에 속하는지 먼저 찾아야 합니다.

단계별 풀이

1. 한 자리 수는 $9$자리, 두 자리 수는 $90\times 2=180$자리, 세 자리 수는 $900\times 3=2700$자리입니다.
2. 계속 빼 나가면 백만 번째 자리는 6자리 수 구간에 들어갑니다.
3. 계산하면 해당 수는 $185185$이고, 그 안의 해당 자리는 첫 번째 자리입니다.
4. 따라서 백만 번째 숫자는 $1$입니다.

헷갈리기 쉬운 점

백만 번째 “수”가 아니라 백만 번째 “자리 숫자”입니다.

13. 팬케이크 뒤집기

문제 한눈에 보기

연속한 팬케이크 무더기 구간 하나를 통째로 뒤집는 연산으로 목표 배열을 최소 횟수에 만드는 문제입니다.

답

$[1,3]$을 뒤집고, 그다음 $[3,5]$를 뒤집는다.

핵심 개념

길이 5 배열이라서 가능한 1회, 2회 뒤집기 결과를 직접 따져볼 수 있습니다.

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

최소 횟수를 묻는 문제이므로, 먼저 1번에 가능한지부터 확인해야 합니다.

단계별 풀이

1. 한 번 뒤집기만으로는 목표 배열이 나오지 않습니다.
2. 첫 연산으로 $[1,3]$을 뒤집으면 배열이 많이 정리됩니다.
3. 이어서 $[3,5]$를 뒤집으면 정확히 목표 배열이 됩니다.
4. 공식 해설에 따르면 이 방법은 유일합니다.

헷갈리기 쉬운 점

구간을 뒤집으면 순서만 바뀌는 것이 아니라 좌우 위치 전체가 뒤집힙니다.

14. 나무 키 순서

문제 한눈에 보기

각 나무마다 “오른쪽에 있는 자기보다 작은 나무 수”가 주어졌을 때, 나무 키를 큰 순서대로 복원하는 문제입니다.

답

$H>C>F>I>G>A>B>J>D>E$

핵심 개념

이 값들은 순열의 inversion 개수와 같습니다.

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

오른쪽의 더 작은 원소 수가 주어진 문제는, 뒤에서부터 하나씩 끼워 넣으면 자연스럽게 복원됩니다.

단계별 풀이

1. 맨 오른쪽 J와 E처럼 값이 0인 나무부터 위치가 쉽게 정해집니다.
2. 뒤에서부터 “자기보다 작은 것이 몇 개 오른쪽에 있어야 하는가”를 만족하도록 하나씩 삽입합니다.
3. 공식 정답 화면의 완성 순서는
   $H>C>F>I>G>A>B>J>D>E$입니다.

헷갈리기 쉬운 점

왼쪽의 더 큰 나무 수가 아니라, 오른쪽의 더 작은 나무 수라는 점을 끝까지 유지해야 합니다.

15. 가장 긴 비밀번호

문제 한눈에 보기

3×3 키패드에서 인접한 칸을 연속해 누를 수 없고, 각 칸은 한 번만 누를 수 있을 때 가장 긴 비밀번호를 찾는 문제입니다.

답

최대 길이는 8이고, 예시는 1-6-3-4-7-2-5-8

핵심 개념

그래프에서 인접 금지 규칙을 만족하는 가장 긴 경로를 찾는 문제입니다.

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

9개 전부를 누를 수 있는지부터 보면 되고, 불가능하면 8개짜리 경로를 찾으면 됩니다.

단계별 풀이

1. 가운데 $5$는 거의 모든 칸과 인접하므로 경로 중간에 쓰기 어렵습니다.
2. 실제로 조건을 모두 만족하며 누를 수 있는 최대 길이는 $8$입니다.
3. 공식 화면의 예시는 $1-6-3-4-7-2-5-8$입니다.
4. 가능한 정답은 여러 개이며, 공식 해설에 따르면 총 $592$개입니다.

헷갈리기 쉬운 점

상하좌우뿐 아니라 대각선으로 닿아도 연속해서 누를 수 없습니다.

16. 곱이 504인 쌍 잇기

문제 한눈에 보기

오름차순 배열과 내림차순 배열에서 하나씩 골라 곱이 $504$가 되는 모든 쌍을 찾는 문제입니다.

답

$(2,252),(7,72),(12,42),(72,7),(168,3)$

핵심 개념

504의 약수를 이용해 각 수의 짝을 찾으면 됩니다.

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

무작정 선을 잇기보다, $504÷x$가 상대 배열에 있는지 확인하는 편이 빠릅니다.

단계별 풀이

1. 위 배열의 각 수 $x$에 대해 $504/x$를 계산합니다.
2. 상대 배열에 실제로 존재하는 경우만 남깁니다.
3. 그 결과 가능한 쌍은
   $(2,252),(7,72),(12,42),(72,7),(168,3)$입니다.

헷갈리기 쉬운 점

배열이 두 개라서 $(7,72)$와 $(72,7)$은 서로 다른 연결입니다.

17. 장난감 기차

문제 한눈에 보기

길이 2칸짜리 다리가 버틸 수 있는 최대 하중이 10g일 때, 인형 순서를 바꿔 다리가 무너지지 않게 하는 문제입니다.

답

예: (8, 2, 6, 4, 3, 7, 1, 9)

핵심 개념

기차가 다리를 지날 때, 동시에 다리 위에 올라가는 인형 두 개의 합이 항상 10 이하여야 합니다.

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

길이가 2칸인 다리이므로 결국 연속한 두 칸의 무게 합 조건으로 바뀝니다.

단계별 풀이

1. 가장 무거운 수끼리는 붙여 놓을 수 없습니다.
2. 큰 수와 작은 수를 번갈아 배치하면 연속 두 칸 합을 줄일 수 있습니다.
3. 공식 해설이 인정한 배치 중 하나는
   $(8,2,6,4,3,7,1,9)$입니다.

헷갈리기 쉬운 점

전체 합이 아니라, 다리 위의 연속 두 칸 합만 조건을 만족하면 됩니다.

18. 나뭇가지 게임

문제 한눈에 보기

무더기 $A=7$, $B=5$에서 번갈아 원하는 만큼 가져가고 마지막 나뭇가지를 가져간 사람이 이기는 게임입니다.

답

처음에 A에서 2개를 가져가 두 무더기를 같게 만들면 이길 수 있다.

핵심 개념

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

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

같은 상태를 상대에게 넘기면, 상대가 무엇을 하든 다시 맞춰서 대응할 수 있기 때문입니다.

단계별 풀이

1. 시작 상태 $(7,5)$는 두 무더기 수가 다릅니다.
2. 먼저 A에서 2개를 가져가 $(5,5)$를 만듭니다.
3. 이후 상대가 한쪽에서 $k$개를 가져가면, 다른 쪽에서도 $k$개를 가져와 다시 같은 상태로 맞춥니다.
4. 결국 마지막 나뭇가지는 내가 가져가게 됩니다.

헷갈리기 쉬운 점

이 게임은 마지막 나뭇가지를 가져가는 사람이 이깁니다.

19. 비버 이동

문제 한눈에 보기

원점에서 시작해 왼쪽으로 3칸 또는 5칸, 오른쪽으로 2칸 또는 7칸만 움직일 수 있을 때, 최소 이동 횟수로 $-2$에 가는 문제입니다.

답

$4$번

핵심 개념

가능한 이동을 식으로 보면 $+2,+2,-3,-3=-2$가 가장 짧습니다.

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

한 번이나 두 번, 세 번으로 가능한지를 먼저 보면서 최소 횟수를 판정해야 하기 때문입니다.

단계별 풀이

1. 1번이나 2번 이동으로는 $-2$를 만들 수 없습니다.
2. 3번 이동도 가능한 합들을 써 보면 $-2$가 나오지 않습니다.
3. 4번 이동에서는 $+2,+2,-3,-3=-2$가 가능합니다.
4. 또 다른 방법으로 $+7,-3,-3,-3=-2$도 가능합니다.

헷갈리기 쉬운 점

이동 순서는 상관없고, 총합이 $-2$가 되는 최소 이동 횟수만 보면 됩니다.

20. 원형 전구 뒤집기

문제 한눈에 보기

원형 전구 5개에서 시계 방향 연속 구간을 뒤집는 연산으로 5번 전구만 켜지게 만드는 최소 연산 횟수를 구합니다.

답

$2$번

핵심 개념

한 번 뒤집기로는 상태를 맞출 수 없고, 두 번이면 가능합니다.

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

최소 횟수 문제이므로 1번으로 가능한지 먼저 확인하면 됩니다.

단계별 풀이

1. 시작 상태에서 한 번의 연산만으로 목표 상태를 만들 수는 없습니다.
2. 두 번 연산으로는 예를 들어 $[(2,3),(5,2)]$가 가능합니다.
3. 공식 해설에는 이와 동치인 6가지 가능한 답이 제시되어 있습니다.

헷갈리기 쉬운 점

$i$에서 $j$까지는 시계 방향으로 이동하는 구간이라는 점을 놓치면 안 됩니다.

개념 한눈에 보기

주제	해당 문제	한 줄 요약
비교와 경우의 수	1, 2, 3, 8	순서 수와 독립 선택 수를 먼저 세면 된다.
시뮬레이션	4, 5, 6, 7, 9	규칙이 고정된 문제는 실제 진행 순서를 추적하는 것이 가장 빠르다.
수열과 자릿수	10, 12	피보나치형 점화식과 자릿수 블록 계산을 쓰면 된다.
게임 전략	18, 19, 20	상대에게 불리한 상태를 넘기거나 최소 이동을 먼저 판단한다.
구성형	13, 14, 15, 16, 17	정답 하나를 만들되 왜 최소인지 같이 확인해야 한다.