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

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

이 문서는 2019 - 고등부 기출문제를 바탕으로, 고등부 1교시 정답 자료를 학습용 풀이 노트로 다시 정리한 것입니다. 계산형은 핵심 수학 아이디어를 보강했고, 구성형은 공식 정답 화면 기준으로 설명을 붙였습니다.

1. 선형 디오판토스

문제 한눈에 보기

$ax+by=48$을 만족하는 정수 $x,y$가 존재하지 않는 경우를 찾는 문제입니다.

답

$a=14,b=21$

핵심 개념

정수해 존재 조건은 $\gcd (a,b)$가 $48$을 나누는가입니다.

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

실제로 $x,y$를 찾기보다 최대공약수 조건 하나로 바로 판정할 수 있습니다.

단계별 풀이

1. 정수해가 존재하려면 $\gcd (a,b)|48$이어야 합니다.
2. $\gcd (14,21)=7$인데 $48$은 $7$의 배수가 아닙니다.
3. 따라서 이 경우만 해가 존재하지 않습니다.

헷갈리기 쉬운 점

두 수가 커도 gcd만 보면 충분합니다.

2. 최대 둘레 사다리꼴

문제 한눈에 보기

주어진 12개 길이 중 4개를 골라 만들 수 있는 사다리꼴 가운데 둘레가 가장 큰 값을 구합니다.

답

$155$

핵심 개념

긴 막대부터 고르되, 실제로 사다리꼴이 되는 길이 조건을 만족해야 합니다.

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

가장 긴 네 개를 무조건 쓰면 도형이 안 만들어질 수 있으므로, 성립 조건을 먼저 확인해야 합니다.

단계별 풀이

1. 큰 길이들부터 조합을 살펴보면, 무조건 둘레가 큰 것이 되는 것은 아닙니다.
2. 공식 정답은 둘레 $155$입니다.
3. 예를 들어 $77,42,24,12$는 실제로 사다리꼴을 만들 수 있고 합이 $155$입니다.

헷갈리기 쉬운 점

막대 네 개를 골랐다고 항상 사각형이 되는 것은 아닙니다.

3. 동심원 칠하기

문제 한눈에 보기

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

답

$256$

핵심 개념

영역 8개가 각각 독립적으로 두 색 중 하나를 고릅니다.

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

각 영역 선택이 서로 영향을 주지 않으므로 곱의 법칙이 바로 적용됩니다.

단계별 풀이

1. 색칠할 영역 수는 총 8개입니다.
2. 각 영역마다 흰색/회색 2가지 선택이 있습니다.
3. 따라서 경우 수는 $2^8=256$입니다.

헷갈리기 쉬운 점

원 개수와 색칠 영역 수가 같다는 점만 놓치지 않으면 됩니다.

4. 369 게임

문제 한눈에 보기

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

답

$503$

핵심 개념

박수는 수 하나당 최대 한 번이므로, 해당 수의 개수를 세면 됩니다.

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

369가 여러 번 들어 있어도 박수는 한 번이라서, 결국 조건을 만족하는 수의 개수 문제입니다.

단계별 풀이

1. $301$부터 $1000$까지 총 700개 수를 봅니다.
2. 자릿수에 $3$, $6$, $9$가 하나라도 포함된 수를 세면 됩니다.
3. 직접 세거나 보수 counting을 하면 총 $503$개입니다.

헷갈리기 쉬운 점

$999$처럼 여러 자리에 있어도 박수는 3번이 아니라 1번입니다.

5. 20번 빼기 연산

문제 한눈에 보기

맨 앞 자릿수 숫자를 빼는 연산을 정확히 20번 적용해 0이 되는 최대 정수를 구합니다.

답

$45$

핵심 개념

연산 횟수는 규칙이 완전히 정해져 있으므로 후보를 직접 따라가면 됩니다.

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

선택의 여지가 없는 과정이라, 각 후보에 대해 실제 횟수를 세는 것이 가장 확실합니다.

단계별 풀이

1. 보기들을 차례로 따라가 보면
   $40$은 $19$번, $42$와 $45$는 $20$번, $86$은 더 많이 걸립니다.
2. 정확히 $20$번이 되는 후보 중 더 큰 수는 $45$입니다.
3. 따라서 정답은 $45$입니다.

헷갈리기 쉬운 점

가장 높은 자릿값이 아니라, 가장 높은 자리의 숫자만 뺍니다.

6. 악수 그래프

문제 한눈에 보기

네 명이 처음 만나 악수했을 때, 모두가 적어도 한 번은 악수한 경우의 수를 세는 문제입니다.

답

$41$

핵심 개념

네 사람의 악수 관계를 그래프로 보면, 고립 정점이 없는 부분그래프 개수를 세는 문제입니다.

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

악수를 두 사람의 연결로 보면 조건이 아주 간단한 그래프 세기 문제로 바뀝니다.

단계별 풀이

1. 네 사람 사이 가능한 악수쌍 수는 $6$개입니다.
2. 전체 부분그래프 수는 $2^6=64$개입니다.
3. 여기서 한 사람 이상이 전혀 악수하지 않은 경우를 제외하면 $41$개가 남습니다.
4. 공식 정답도 $41$입니다.

헷갈리기 쉬운 점

악수 순서를 세는 게 아니라, 실제로 악수한 “쌍들의 집합”만 셉니다.

7. 이진수에서 연속된 1

문제 한눈에 보기

$1$ 이상 $255$ 이하 자연수 중, 이진수로 썼을 때 $11$이 한 번도 나타나지 않는 수의 개수를 구합니다.

답

$54$

핵심 개념

연속된 1이 없는 이진수 개수는 피보나치형 점화식을 따릅니다.

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

길이별로 세면, 마지막 자리가 $0$인지 $1$인지에 따라 자연스럽게 점화식이 생깁니다.

단계별 풀이

1. 길이 $n$ 이진수 중 연속된 1이 없는 개수를 $f(n)$이라 하면 $f(n)=f(n-1)+f(n-2)$입니다.
2. $255$ 이하 수는 최대 8비트입니다.
3. 1비트부터 8비트까지의 유효한 수를 모두 합하면 $54$개입니다.

헷갈리기 쉬운 점

$0$은 범위에 포함되지 않으므로 마지막에 빼 주어야 합니다.

8. 25마리 말

문제 한눈에 보기

한 번에 5마리씩만 경주할 수 있고, 순위만 알 수 있을 때 가장 빠른 말 3마리를 찾는 최소 경주 횟수를 구합니다.

답

$7$

핵심 개념

처음 5번 경주로 각 조 내부 순서를 알고, 후보를 최대한 줄인 뒤 마지막 경주로 결정합니다.

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

전체 순서를 다 알 필요 없이, top 3 후보만 남기면 됩니다.

단계별 풀이

1. 25마리를 5조로 나누어 5번 경주합니다.
2. 각 조 1등끼리 한 번 더 경주하면 top 3이 나올 수 있는 조가 크게 줄어듭니다.
3. 마지막 한 번으로 남은 후보들을 겨루면 전체 top 3를 확정할 수 있습니다.
4. 따라서 최소는 $7$번입니다.

헷갈리기 쉬운 점

시계가 없어서 시간 차이는 모르고, 같은 경주 안의 상대 순위만 알 수 있습니다.

9. 성냥 정다각형 쌍

문제 한눈에 보기

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

답

$36$

핵심 개념

각 쌍마다 양의 배수 합으로 표현 가능한 공통 수를 찾으면 됩니다.

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

모든 쌍을 동시에 만족해야 하므로 공통 가능한 가장 작은 수를 찾는 문제입니다.

단계별 풀이

1. $36$은 여러 쌍에 대해 적절한 배수 합으로 표현됩니다.
2. 실제로 여섯 쌍 모두가 $36$개 성냥으로 가능합니다.
3. 공식 정답은 $36$입니다.

헷갈리기 쉬운 점

각 도형은 반드시 한 개 이상은 만들어야 합니다.

10. 철도망 경로 수

문제 한눈에 보기

에지를 최대 한 번만 사용하면서 A에서 E로 가는 서로 다른 길의 개수를 세는 문제입니다.

답

$70$

핵심 개념

중앙의 여러 개 루프를 어떻게 드나드느냐를 경우의 수로 세는 문제입니다.

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

같은 도시를 다시 지나는 것은 허용되지만, 같은 철도는 다시 못 쓰므로 에지 사용 패턴을 봐야 합니다.

단계별 풀이

1. A-B와 D-E는 반드시 한 번씩 써야 합니다.
2. 따라서 핵심은 B, C, D 사이의 여러 철도를 한 번씩만 쓰며 B에서 D로 가는 방법 수입니다.
3. 이를 경우 분류하면 공식 정답 $70$이 나옵니다.

헷갈리기 쉬운 점

도시 재방문은 가능하지만, 이미 쓴 철도 재사용은 금지입니다.

11. 200번째 회문

문제 한눈에 보기

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

답

cbbababbc

핵심 개념

회문은 앞의 5글자만 정하면 나머지가 자동 결정됩니다.

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

전체 243개를 직접 나열하지 않고도 200번째를 정확히 찾을 수 있습니다.

단계별 풀이

1. 가능한 회문 수는 $3^5=243$개입니다.
2. 사전순 200번째 앞 5글자는 cbbab입니다.
3. 이를 대칭으로 붙이면 cbbababbc가 됩니다.

헷갈리기 쉬운 점

중앙 글자까지 포함한 5글자가 자유롭습니다.

12. 2백만 번째 숫자

문제 한눈에 보기

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

답

$5$

핵심 개념

자리 수 구간별 자릿수를 차례로 빼 가는 전형적인 자릿수 문제입니다.

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

2백만 자리까지 직접 이어 쓰는 것은 불가능하므로, 어느 수에 속하는지 먼저 찾아야 합니다.

단계별 풀이

1. 한 자리 수부터 차례로 자릿수를 뺍니다.
2. 2백만 번째 자리는 6자리 수 구간에 들어갑니다.
3. 계산하면 해당 수는 $351851$이고, 그 안의 해당 자리는 마지막 자리 $5$입니다.

헷갈리기 쉬운 점

2백만 번째 “자릿수”이지, 2백만 번째 “정수”가 아닙니다.

13. 팬케이크 뒤집기

문제 한눈에 보기

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

답

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

핵심 개념

짧은 배열이라 1회, 2회 연산으로 가능한 상태를 직접 확인할 수 있습니다.

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

최소 횟수를 묻기 때문에 가장 짧은 연산 수부터 가능 여부를 보는 것이 자연스럽습니다.

단계별 풀이

1. 한 번 뒤집기로는 목표 배열을 만들 수 없습니다.
2. $[1,3]$ 뒤집기 후 $[3,5]$를 뒤집으면 목표 배열이 됩니다.
3. 공식 해설에 따르면 이 해는 유일합니다.

헷갈리기 쉬운 점

선택한 구간 전체 순서가 거꾸로 됩니다.

14. 저장소 배치

문제 한눈에 보기

트리형 저장소 $a,b,c,d,e,f$에 숫자 $16$을 배치해, $1,2,1,6,2,1,1,6$을 읽는 총 시간을 최소화하는 문제입니다.

답

예: a=1, b=6, c=2, d=5, e=4, f=3

핵심 개념

자주 읽는 값일수록 루트 X에 가까운 위치에 두는 것이 유리합니다.

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

읽는 시간이 곧 깊이이므로, 등장 횟수와 중요도가 높은 값을 얕은 위치에 둬야 합니다.

단계별 풀이

1. 가장 자주 등장하는 값은 $1$, 그다음 핵심 후보는 $2$와 $6$입니다.
2. 따라서 $a,b$처럼 깊이 1인 위치에는 반드시 $1$과 2 또는 6이 와야 합니다.
3. 공식 예시는 $a=1,b=6,c=2,d=5,e=4,f=3$입니다.
4. 해설에 따르면 이런 형태의 최적 배치는 총 96가지 있습니다.

헷갈리기 쉬운 점

등장 횟수만 같다고 아무 데나 두면 안 되고, 읽기 순서 전체 합을 최소로 해야 합니다.

15. 비버 이동

문제 한눈에 보기

왼쪽으로 3칸 또는 5칸, 오른쪽으로 2칸 또는 7칸만 움직여 원점에서 $-2$에 최소 횟수로 가는 문제입니다.

답

$4$번

핵심 개념

작은 이동 수부터 가능한 합을 점검하면 됩니다.

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

최소 횟수 문제라 1번, 2번, 3번으로 안 되는 것을 먼저 확인해야 합니다.

단계별 풀이

1. 1~3번 이동으로는 $-2$를 만들 수 없습니다.
2. 4번 이동에서는 $+2,+2,-3,-3=-2$가 가능합니다.
3. 또 $+7,-3,-3,-3=-2$도 가능합니다.

헷갈리기 쉬운 점

순서는 중요하지 않고 총합만 맞으면 됩니다.

16. 조리 순서

문제 한눈에 보기

프라이팬 1개, 냄비 1개만 있을 때 세 가지 요리를 모두 가장 빨리 완성하는 순서를 찾는 문제입니다.

답

최소 $5$분

핵심 개념

두 도구를 최대한 쉬지 않게 병렬로 돌리는 스케줄링 문제입니다.

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

전체 작업 수보다 “프라이팬만 필요한 구간”, “냄비만 필요한 구간”이 어떻게 겹치는지가 중요합니다.

단계별 풀이

1. 각 요리의 작업 순서를 보면서 프라이팬과 냄비 사용 시간을 겹치게 배치합니다.
2. 중간에 도구를 바꿔 다른 요리를 끼워 넣을 수 있습니다.
3. 공식 해설은 모든 요리를 $5$분 안에 완성하면 정답이라고 설명합니다.

헷갈리기 쉬운 점

한 요리를 처음부터 끝까지 다 하고 다음 요리를 하는 방식이 아닙니다.

17. 원형 전구 뒤집기

문제 한눈에 보기

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

답

$2$번

핵심 개념

한 번 연산으로는 목표 상태를 만들 수 없고, 두 번이면 가능합니다.

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

최소 횟수 문제이므로 1번 가능 여부부터 확인하는 것이 가장 빠릅니다.

단계별 풀이

1. 한 번의 뒤집기로는 목표 상태가 되지 않습니다.
2. 예를 들어 $[(2,3),(5,2)]$ 두 번이면 가능합니다.
3. 공식 해설에는 이와 동치인 여러 최적 해가 제시되어 있습니다.

헷갈리기 쉬운 점

구간은 반드시 시계 방향으로 읽어야 합니다.

18. 학생 식당

문제 한눈에 보기

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

답

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

핵심 개념

이전 날 식당만 기억하면 되는 DP 문제입니다.

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

오늘 선택 가능한 식당은 어제 간 식당 하나만 금지되기 때문입니다.

단계별 풀이

1. 각 날짜와 마지막 식당에 대해 최소 비용을 계산합니다.
2. 끝까지 계산하면 최소 총비용은 $6$입니다.
3. 최적 선택은 $B\to A\to C\to A\to B$입니다.

헷갈리기 쉬운 점

매일 그날의 최저가만 고르면 연속 금지 때문에 전체 최적이 아닐 수 있습니다.

19. 2×20 칸 게임

문제 한눈에 보기

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

답

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

핵심 개념

이 게임은 간단한 불변량으로 winning 상태를 유지할 수 있습니다.

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

칸 수가 많아 전부 경우분석하기보다, 유지할 상태 하나를 찾는 것이 훨씬 효율적입니다.

단계별 풀이

1. 위쪽 죽은 칸 수를 $x$, 아래쪽을 $y$라 둡니다.
2. 공식 해설은 $x-y=1$ 상태를 계속 유지하면 선공이 이긴다고 설명합니다.
3. 상대가 무엇을 하든 적절한 칸을 골라 다시 이 상태로 맞출 수 있습니다.

헷갈리기 쉬운 점

제일 왼쪽 아래 칸을 고르면 지는 특수 규칙도 함께 고려해야 합니다.

20. 자율주행 자동차

문제 한눈에 보기

각 블록을 누를 때마다 길 모양이 시계 방향으로 90도 회전할 때, 자동차가 목표 지점까지 가게 만드는 최소 회전 횟수를 구합니다.

답

$13$회

핵심 개념

각 칸의 회전 횟수를 조정해 시작점에서 도착점까지 하나의 연속 경로를 만들어야 합니다.

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

회전을 많이 할수록 손해이므로, 전체 경로를 먼저 상상하고 필요한 칸만 최소만큼 돌려야 합니다.

단계별 풀이

1. 시작에서 도착까지 연결될 길을 하나 정합니다.
2. 각 칸이 그 경로에 맞도록 필요한 최소 회전 수만 적용합니다.
3. 공식 정답 자료의 최소 회전 횟수는 $13$입니다.

헷갈리기 쉬운 점

한 칸을 여러 번 누를 수 있지만, 4번 누르면 원상복구라서 항상 최소 회전수로 생각해야 합니다.

개념 한눈에 보기

주제	해당 문제	한 줄 요약
정수와 나머지	1, 4, 5, 12	최대공약수, counting, 연산 시뮬레이션, 자릿수 계산을 쓴다.
경우의 수와 그래프	6, 7, 8, 10, 11	부분그래프 개수, 피보나치형 counting, 후보 줄이기, 경로 수를 센다.
구성형	13, 14, 16, 17, 18, 20	최적 배치를 하나 찾고 왜 최소인지까지 확인한다.
게임 전략	15, 19	최소 이동 횟수와 불변량 유지가 핵심이다.