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

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

이 문서는 2019 - 중등부 기출문제를 바탕으로, 중등부 1교시 정답 자료를 다시 읽기 쉽게 정리한 학습용 풀이 노트입니다. 유형 2 문제는 공식 정답 화면과 핵심 전략을 함께 정리했습니다.

1. 곱의 이진수 끝자리

문제 한눈에 보기

$2019\times 2021$을 이진수로 썼을 때, 맨 오른쪽에 연속해서 나타나는 $1$의 개수를 구하는 문제입니다.

답

$4$

핵심 개념

홀수 N의 끝에 붙는 연속된 1의 개수는 $N+1$의 2로 나누어지는 횟수와 같습니다.

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

이진수를 직접 곱해 쓰는 대신, $N+1$의 2의 거듭제곱 인수를 보면 훨씬 빠릅니다.

단계별 풀이

1. $2019\times 2021=(2020-1)(2020+1)=2020^2-1$입니다.
2. 따라서 $N+1=2020^2$입니다.
3. $2020=4\times 505$이므로 $2020^2$는 $2^4$를 인수로 가집니다.
4. 따라서 이진수 끝의 연속된 1의 개수는 $4$입니다.

헷갈리기 쉬운 점

끝의 0 개수와 헷갈리면 안 됩니다. 이 문제는 끝의 연속된 1 개수입니다.

2. 빠진 수 찾기

문제 한눈에 보기

$3$부터 $15$까지 연속된 수 중 정확히 하나를 뺐더니 합이 $106$이었습니다. 빠진 수를 구합니다.

답

$11$

핵심 개념

전체 합에서 남은 합을 빼면 빠진 수가 바로 나옵니다.

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

직접 맞춰 보기보다 전체 합을 한 번 계산하는 편이 가장 짧습니다.

단계별 풀이

1. $3$부터 $15$까지 합은
   $1$부터 $15$까지 합 $120$에서 $1+2=3$을 빼서 $117$입니다.
2. 빠진 수는 $117-106=11$입니다.

헷갈리기 쉬운 점

구간이 $1$부터가 아니라 $3$부터라는 점만 조심하면 됩니다.

3. 마야 숫자

문제 한눈에 보기

마야의 20진수 두 자리 숫자를 10진수로 바꾸는 문제입니다.

답

$333$

핵심 개념

두 자리 20진수는 $\text{윗자리}\times 20+\text{아랫자리}$로 계산합니다.

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

기호만 해석하면 나머지는 평범한 진법 변환 문제입니다.

단계별 풀이

1. 그림의 윗자리는 점 1개와 막대 3개로 $16$입니다.
2. 아랫자리는 점 3개와 막대 2개로 $13$입니다.
3. 따라서 값은 $16\times 20+13=333$입니다.

헷갈리기 쉬운 점

10진수 두 자리처럼 이어 읽는 것이 아니라 20진수 자리값을 써야 합니다.

4. 군인과 어린이의 배

문제 한눈에 보기

성인 군인 20명을 강 건너편으로 보내되, 작은 배는 “어린이 2명 이하” 또는 “어른 1명”만 태울 수 있을 때 최소 왕복 횟수를 구합니다.

답

$80$

핵심 개념

어른 한 명을 보내고 시스템을 원상복구하려면 배가 4번 움직여야 합니다.

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

어른은 혼자만 탈 수 있어서, 어린이 둘이 배를 계속 되돌려 주는 구조를 먼저 봐야 합니다.

단계별 풀이

1. 어린이 2명이 먼저 건넙니다.
2. 어린이 1명이 돌아옵니다.
3. 어른 1명이 건넙니다.
4. 반대편에 있던 어린이 1명이 돌아옵니다.
5. 이렇게 해야 어른 1명이 건너고 다시 시작 상태가 됩니다.
6. 어른 20명에 대해 $4\times 20=80$번입니다.

헷갈리기 쉬운 점

어른 둘이 같이 탈 수 없기 때문에, 한 번에 여러 군인을 보내는 방법은 없습니다.

5. 400년 뒤 요일

문제 한눈에 보기

오늘이 M월 D일 월요일일 때, 400년 뒤 같은 날짜의 요일을 묻는 문제입니다.

답

월요일

핵심 개념

그레고리력에서 400년은 정확히 7일 주기의 정수배입니다.

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

윤년 규칙이 복잡해 보여도, 400년 단위로 보면 완전히 한 주기가 닫힙니다.

단계별 풀이

1. 400년 동안 윤년은 $97$번 있습니다.
2. 전체 날짜 수는 $400\times 365+97=146097$일입니다.
3. $146097=7\times 20871$이므로 정확히 7의 배수입니다.
4. 따라서 요일은 변하지 않아 여전히 월요일입니다.

헷갈리기 쉬운 점

4년, 100년, 400년 규칙을 모두 반영해야 정확히 맞습니다.

6. 두붓그리기

문제 한눈에 보기

한붓그리기는 안 되지만, 정확히 두 번으로는 그릴 수 있는 도형을 찾는 문제입니다.

답

정사각형 안에 대각선 두 개가 교차한 도형

핵심 개념

그래프의 홀수 차수 정점 개수를 세면 됩니다.

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

그림을 직접 손으로 따라가기보다, 오일러 경로 조건으로 판정하는 편이 정확합니다.

단계별 풀이

1. 한붓그리기가 가능하려면 홀수 차수 정점이 $0$개 또는 $2$개여야 합니다.
2. 두 번에 그릴 수 있으려면 홀수 차수 정점이 최대 $4$개면 됩니다.
3. 정사각형 안에 X가 그어진 도형은 네 꼭짓점 차수가 모두 $3$이라 홀수 정점이 $4$개입니다.
4. 따라서 한붓그리기는 불가능하지만 두붓그리기는 가능합니다.

헷갈리기 쉬운 점

중앙 교점도 하나의 정점으로 세야 합니다.

7. 제조 공정 스케줄

문제 한눈에 보기

12개 작업이 방향그래프로 주어질 때, 장인 2명이 작업하면 완성까지 최소 시간이 몇 시간인지 구하는 문제입니다.

답

$7$시간

핵심 개념

선행 조건과 병렬 가능 작업을 함께 봐서 매 시간 두 사람을 최대한 쉬지 않게 배치해야 합니다.

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

최장 경로만 보는 것으로는 부족하고, 두 사람이 동시에 일할 수 있는 구간도 고려해야 합니다.

단계별 풀이

1. 한 가능한 최적 스케줄은
   $1,2$ → $3,4$ → $5,6$ → $7,8$ → $9,10$ → $11$ → $12$입니다.
2. 각 단계의 선행 조건을 모두 만족합니다.
3. 총 $7$시간에 끝낼 수 있고, 공식 정답도 $7$입니다.

헷갈리기 쉬운 점

한 사람이 빈다고 해서 바로 끝나는 것은 아닙니다. 마지막 $11\to 12$ 사슬이 남습니다.

8. 하노이 탑 두 장 옮기기

문제 한눈에 보기

하노이 탑에서 한 번에 한 장 또는 두 장을 옮길 수 있을 때, 원판 7개를 다른 기둥으로 옮기는 최소 횟수를 구합니다.

답

$15$

핵심 개념

작은 원판 둘을 한 번에 옮길 수 있어 일반 하노이 탑보다 훨씬 빨라집니다.

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

기존의 $2^n-1$ 공식을 그대로 쓰면 안 되고, 새 규칙에 맞는 최적 전략을 봐야 합니다.

단계별 풀이

1. 두 장을 한 번에 옮길 수 있으므로 작은 원판 이동을 묶어서 줄일 수 있습니다.
2. 공식 정답 자료의 최적 계산 결과, 원판 7개는 $15$번이면 충분합니다.
3. 일반 하노이 탑의 $127$번보다 크게 줄어든 값입니다.

헷갈리기 쉬운 점

두 장을 옮길 때도 여전히 큰 원판이 작은 원판 위에 올라갈 수는 없습니다.

9. 200번째 회문

문제 한눈에 보기

$a,b,c$로 만드는 길이 9 회문을 사전순으로 나열했을 때 200번째 문자열을 구하는 문제입니다.

답

cbbababbc

핵심 개념

길이 9 회문은 앞 5글자만 정하면 되므로, 사실상 길이 5 문자열의 사전순과 같습니다.

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

243개 전체를 다 쓰지 않고도, 앞 5자리 기준으로 위치를 바로 찾을 수 있습니다.

단계별 풀이

1. 가능한 회문 수는 $3^5=243$개입니다.
2. 회문의 사전순은 앞의 5글자 사전순과 정확히 일치합니다.
3. 200번째 앞부분은 cbbab이고, 이를 대칭으로 붙이면 cbbababbc입니다.

헷갈리기 쉬운 점

앞 4글자가 아니라 가운데 포함 5글자를 정해야 합니다.

10. 2×10 타일 채우기

문제 한눈에 보기

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

답

$89$

핵심 개념

첫 열을 세로 1장으로 채우거나, 가로 2장으로 채우는 경우로 분할합니다.

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

맨 왼쪽 선택이 정해지면 나머지는 같은 형태의 작은 문제로 줄어듭니다.

단계별 풀이

1. $f(n)=f(n-1)+f(n-2)$입니다.
2. $f(1)=1$, $f(2)=2$입니다.
3. 피보나치처럼 계산하면 $f(10)=89$입니다.

헷갈리기 쉬운 점

가로 타일은 두 장이 함께 들어간다는 점을 잊지 말아야 합니다.

11. 성냥 정다각형 쌍

문제 한눈에 보기

정삼각형, 정사각형, 정오각형, 정육각형의 모든 쌍을, 박스 속 성냥을 전부 써서 만들 수 있는 최소 성냥 수를 구합니다.

답

$36$

핵심 개념

각 쌍마다 “양의 배수 합”으로 표현 가능해야 합니다.

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

모든 쌍을 한 번에 만족해야 하므로, 작은 수부터 시험하면 가장 먼저 되는 공통 수를 찾을 수 있습니다.

단계별 풀이

1. $36$은
   12+24 (정사각형+정육각형),
   21+15 (정삼각형+정오각형),
   16+20 (정사각형+정오각형)처럼 여러 쌍에 맞습니다.
2. 나머지 쌍들도 $36$으로 모두 표현할 수 있습니다.
3. 공식 정답은 $36$입니다.

헷갈리기 쉬운 점

각 도형은 최소 하나는 만들어야 하므로 0개는 허용되지 않습니다.

12. 백만 번째 숫자

문제 한눈에 보기

$1234567891011\cdots$에서 백만 번째 자리에 오는 숫자를 구합니다.

답

$1$

핵심 개념

자리 수 구간을 한 덩어리씩 빼 가는 자릿수 문제입니다.

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

백만 번째까지 직접 쓸 수는 없으므로, 어느 자리수 구간에 속하는지 먼저 찾아야 합니다.

단계별 풀이

1. 한 자리, 두 자리, 세 자리, … 구간이 차지하는 자릿수를 차례로 뺍니다.
2. 백만 번째 자리는 6자리 수 구간에 들어갑니다.
3. 계산하면 해당 수는 $185185$, 해당 자리는 첫 자리이므로 숫자는 $1$입니다.

헷갈리기 쉬운 점

백만 번째 “정수”가 아닙니다. 이어 쓴 문자열의 백만 번째 자리입니다.

13. 팬케이크 뒤집기

문제 한눈에 보기

연속 구간을 뒤집는 연산으로 팬케이크 배열을 목표 모양으로 최소 횟수에 만드는 문제입니다.

답

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

핵심 개념

길이 5 배열이라 가능한 짧은 연산들을 직접 확인할 수 있습니다.

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

최소 횟수 문제라 1번으로 되는지, 안 되면 2번 해를 찾는 순서가 자연스럽습니다.

단계별 풀이

1. 한 번 뒤집기로는 목표 배열이 되지 않습니다.
2. $[1,3]$ 뒤집기 후 $[3,5]$를 뒤집으면 정확히 목표가 됩니다.
3. 공식 해설에 따르면 이 해는 유일합니다.

헷갈리기 쉬운 점

선택한 양 끝 구간 전체가 통째로 좌우 반전됩니다.

14. 곱이 504인 쌍 잇기

문제 한눈에 보기

두 배열에서 하나씩 골라 곱이 $504$가 되는 모든 경우를 연결하는 문제입니다.

답

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

핵심 개념

각 수의 짝 $504÷x$가 상대 배열에 있는지만 확인하면 됩니다.

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

배열이 정렬되어 있어도, 핵심은 약수 짝을 찾는 것입니다.

단계별 풀이

1. 위 배열의 각 원소에 대해 $504/x$를 계산합니다.
2. 아래 배열에 실제 존재하는 값만 남깁니다.
3. 가능한 연결은 $5$개이며, 위의 다섯 쌍이 전부입니다.

헷갈리기 쉬운 점

두 배열의 순서가 다르므로 $(7,72)$와 $(72,7)$은 서로 다른 연결입니다.

15. 원형 빵 고르기

문제 한눈에 보기

원형으로 놓인 빵들 중 시계 방향으로 연속한 구간을 골라, 좋아하는 정도 합을 최대로 만드는 문제입니다.

답

최대 합은 13

핵심 개념

원형 배열 최대 부분합 문제로 볼 수 있습니다.

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

“연속 구간”만 고를 수 있으므로, 전부 고르거나 한 구간만 빼는 방식으로 생각하면 빨라집니다.

단계별 풀이

1. 공식 해설에 따르면 값이 $-2$인 빵 하나만 빼고 나머지를 모두 고르면 됩니다.
2. 그러면 총합이 $13$이 됩니다.
3. 그림에서 $-2$가 3개 있으므로 가능한 최적 구간도 3가지입니다.

헷갈리기 쉬운 점

원형이므로 끝과 끝도 이어져 있습니다.

16. 전광판 버튼

문제 한눈에 보기

버튼을 누르면 위, 위왼쪽, 위오른쪽 화면이 뒤집히는 전광판을 모두 0으로 만드는 최소 버튼 수를 구합니다.

답

1번, 3번, 5번 버튼을 누른다.

핵심 개념

아래 줄 버튼을 누르면 바로 윗줄에만 영향이 가므로, 왼쪽부터 필요한 버튼을 결정하면 됩니다.

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

한 줄을 맞추기 위해 쓸 수 있는 정보가 바로 아래 버튼뿐이라, 그리디가 자연스럽습니다.

단계별 풀이

1. 맨 위 화면들을 0으로 만들도록 아래 버튼을 왼쪽부터 정합니다.
2. 계산하면 $1,3,5$번 버튼을 누르면 전체가 0이 됩니다.
3. 공식 정답도 최소 $3$번입니다.

헷갈리기 쉬운 점

버튼을 누른 순서는 중요하지 않고, 어떤 버튼들을 누르느냐가 중요합니다.

17. 술래잡기 위치 찾기

문제 한눈에 보기

탑은 주변에 없고, 나무와 바위는 주변에 있다는 답을 들었을 때, 주연이가 있을 수 있는 칸을 모두 찾는 문제입니다.

답

공식 정답 그림의 분홍색 4칸

핵심 개념

맨해튼 거리 $4$ 이하 조건의 교집합과 여집합을 구하는 문제입니다.

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

각 질문은 가능한 칸의 집합 하나를 주므로, 결국 집합의 교집합 계산입니다.

단계별 풀이

1. 두 나무와 바위로부터 거리 $4$ 이하인 칸을 각각 표시합니다.
2. 탑으로부터 거리 $4$ 이하인 칸은 모두 제외합니다.
3. 세 조건을 동시에 만족하는 칸만 남기면 공식 그림의 분홍색 4칸이 됩니다.

헷갈리기 쉬운 점

대각선 거리가 아니라 가로세로 거리의 합, 즉 맨해튼 거리를 써야 합니다.

18. 학생 식당

문제 한눈에 보기

5일 동안 같은 식당을 이틀 연속 가지 않으면서 점심값 총합을 최소로 만드는 선택을 구합니다.

답

$B\to A\to C\to A\to B$, 총 $6$

핵심 개념

날짜가 5일뿐이라 이전 식당만 기억하는 DP로 쉽게 풀립니다.

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

오늘 어느 식당을 고를지는 “어제 어디를 갔는가”에만 영향을 받습니다.

단계별 풀이

1. 각 날짜, 각 식당에 대해 “그 식당으로 끝나는 최소 비용”을 계산합니다.
2. 마지막 날까지 계산하면 최소 비용은 $6$입니다.
3. 그 경로는 $B\to A\to C\to A\to B$입니다.

헷갈리기 쉬운 점

매일 가장 싼 식당을 고르는 greedy는 연속 금지 때문에 실패할 수 있습니다.

19. 2×20 칸 게임

문제 한눈에 보기

2×20 격자에서 칸을 고르면 그 칸의 오른쪽, 위쪽, 오른쪽 위 칸들이 모두 죽는 게임에서 선공이 이기는 전략을 찾는 문제입니다.

답

항상 위쪽 죽은 칸 수 - 아래쪽 죽은 칸 수 = 1 이 되게 만들면 된다.

핵심 개념

winning/losing 상태를 간단한 불변량으로 표현할 수 있습니다.

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

칸이 너무 많아 전부 나열하기 어렵기 때문에, 유지해야 하는 상태 하나를 잡는 것이 핵심입니다.

단계별 풀이

1. 위쪽에서 죽은 칸 수를 $x$, 아래쪽을 $y$라 둡니다.
2. 공식 해설은 $x-y=1$ 상태를 상대에게 계속 넘기면 이길 수 있다고 설명합니다.
3. 상대가 어느 칸을 고르든 다시 이 상태로 맞출 수 있습니다.

헷갈리기 쉬운 점

제일 왼쪽 아래 칸을 고르는 순간 바로 진다는 특수 규칙을 함께 봐야 합니다.

20. 병든 나이트

문제 한눈에 보기

한 방향으로는 못 움직이는 병든 나이트가 장애물을 피해 깃발까지 가는 최소 이동 횟수를 구하는 문제입니다.

답

$8$번

핵심 개념

격자 최단거리 문제이므로 BFS로 보면 됩니다.

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

모든 이동의 비용이 같고, 장애물만 피하면 되므로 최단경로 탐색이 정석입니다.

단계별 풀이

1. 시작칸에서 갈 수 있는 칸들을 1번 이동, 2번 이동, … 순서로 넓혀 갑니다.
2. 장애물 칸은 큐에 넣지 않습니다.
3. 처음으로 깃발 칸에 도달하는 거리가 최소 이동 횟수입니다.
4. 공식 정답 자료에서는 최소 $8$번입니다.

헷갈리기 쉬운 점

원래 나이트의 8방향이 아니라, 문제에서 허용한 7방향만 써야 합니다.

개념 한눈에 보기

주제	해당 문제	한 줄 요약
수와 진법	1, 2, 3	곱셈 구조, 전체 합, 진법 해석을 이용한다.
그래프와 경로	6, 7, 17, 20	차수 판정, 작업 그래프, 거리 집합, BFS를 쓴다.
점화식	8, 9, 10, 12	작은 값에서 큰 값으로 가는 규칙을 잡으면 된다.
구성형	13, 14, 15, 16, 18	정답 배치를 찾고 왜 최적인지 함께 설명해야 한다.
게임 전략	4, 19	시스템을 원상복구하거나 불변량을 유지하는 전략이 핵심이다.