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

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

이 문서는 2020 - 중등부 기출문제를 바탕으로, 중등부 1교시 정답 자료를 다시 읽기 쉽게 정리한 학습용 풀이 노트입니다. 유형 2 문제는 공식 정답 화면을 함께 넣고, 계산형 문제는 핵심 원리를 짧게 덧붙였습니다.

1. 페르마와 나머지

문제 한눈에 보기

소수 $p$에 대해 $a^{p-1}\equiv 1(\mathrm{mod}p)$라는 사실을 이용해 $7^{2020}\mathrm{mod}5$를 구하는 문제입니다.

답

$1$

핵심 개념

소수에 대한 거듭제곱 나머지는 매우 짧은 주기를 가집니다.

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

$7^{2020}$을 계산할 필요 없이, 밑을 $5$로 나눈 나머지와 지수의 주기만 보면 됩니다.

단계별 풀이

1. $7\equiv 2(\mathrm{mod}5)$이므로 $7^{2020}\equiv 2^{2020}(\mathrm{mod}5)$입니다.
2. $2^4=16\equiv 1(\mathrm{mod}5)$입니다.
3. $2020=4\times 505$이므로 $2^{2020}=(2^4{)}^{505}\equiv 1^{505}\equiv 1(\mathrm{mod}5)$입니다.

헷갈리기 쉬운 점

페르마 소정리를 외워도 결국 지금 문제에서는 $4$주기만 써 주면 끝납니다.

2. 가위바위보 확률

문제 한눈에 보기

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

답

$11/16$

핵심 개념

A가 몇 판 만에 우승하는지에 따라 경우를 나누면 됩니다.

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

판 수가 적고, 게임은 누군가 3승을 찍는 순간 끝나므로 경우 분류가 가장 깔끔합니다.

단계별 풀이

1. A는 앞으로 2승만 더 하면 됩니다.
2. 2판 만에 이길 확률은 WW 한 가지이므로 $1/4$입니다.
3. 3판 만에 이길 확률은 WLW, LWW 두 가지이므로 $2/8=1/4$입니다.
4. 4판 만에 이길 확률은 마지막 판이 W이고, 앞 3판에 W 1개 L 2개가 있어야 하므로 $3/16$입니다.
5. 합치면 $1/4+1/4+3/16=11/16$입니다.

헷갈리기 쉬운 점

이미 우승이 결정된 뒤의 가상 추가 판은 세면 안 됩니다.

3. 지뢰찾기

문제 한눈에 보기

보드에 드러난 숫자 조건을 모두 만족할 때, 가~마 가운데 반드시 지뢰인 칸을 찾는 문제입니다.

답

가

핵심 개념

숫자 칸마다 주변 지뢰 수를 식으로 세우면 강제되는 칸이 생깁니다.

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

지뢰찾기는 눈으로 추측하는 문제가 아니라, $0$, $1$, $3$, $5$ 같은 숫자를 순서대로 적용하는 논리 문제입니다.

단계별 풀이

1. $0$이 적힌 칸 주변은 모두 지뢰가 아닙니다.
2. 윗줄의 $1$과 오른쪽의 $1$을 함께 보면 윗부분 후보가 거의 하나로 줄어듭니다.
3. 가운데의 두 $3$과 아래 $5$를 차례로 맞추면 가만은 반드시 지뢰여야 합니다.
4. 따라서 정답은 가입니다.

헷갈리기 쉬운 점

“가능한 지뢰”와 “반드시 지뢰”를 구분해야 합니다.

4. 버블 정렬 3회

문제 한눈에 보기

주어진 배열에 버블 정렬의 한 단계를 세 번 반복한 뒤, 오른쪽에서 세 번째 값이 무엇인지 묻는 문제입니다.

답

$11$

핵심 개념

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

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

전체 배열을 끝까지 정렬할 필요 없이, 세 번만 진행해 오른쪽 끝 근처 값만 보면 되기 때문입니다.

단계별 풀이

1. 1회 수행 뒤에는 가장 큰 값 $15$가 맨 뒤로 갑니다.
2. 2회 수행 뒤에는 그다음 큰 값 $12$가 뒤에서 두 번째로 확정됩니다.
3. 3회 수행 뒤에는 $11$이 뒤에서 세 번째 자리에 놓입니다.

헷갈리기 쉬운 점

버블 정렬의 “한 단계”는 한 번의 교환이 아니라 왼쪽부터 오른쪽 끝까지 한 바퀴 도는 것입니다.

5. 금화 상자

문제 한눈에 보기

세 문장 중 정확히 하나만 참이고, 금화는 상자 하나에만 있을 때 가능한 상자를 찾는 문제입니다.

답

$2$번

핵심 개념

가능한 세 경우를 직접 넣어 보면 참거짓 수가 즉시 드러납니다.

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

문장이 짧고 경우 수도 3개뿐이라, 논리식을 길게 세우는 것보다 직접 대입이 빠릅니다.

단계별 풀이

1. 금화가 1번이면 참이 2개입니다.
2. 금화가 2번이면 참이 정확히 1개입니다.
3. 금화가 3번이면 참이 2개입니다.
4. 따라서 가능한 경우는 2번뿐입니다.

헷갈리기 쉬운 점

한 문장만 맞아야 하므로, 참이 0개인 경우도 2개인 경우도 모두 탈락입니다.

6. 더 큰 수 확률

문제 한눈에 보기

A, B가 각각 1부터 20까지 균등하게 수를 하나 고를 때 $A>B$일 확률을 구하는 문제입니다.

답

$19/40$

핵심 개념

$A>B$와 $A<B$는 대칭이고, 같은 수를 고르는 경우만 따로 빼 주면 됩니다.

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

400가지 경우를 하나하나 세는 것보다, 대칭과 동률 개수를 먼저 보는 편이 훨씬 빠릅니다.

단계별 풀이

1. 전체 경우 수는 $20\times 20=400$입니다.
2. $A=B$인 경우는 $20$가지입니다.
3. 나머지 $380$가지는 $A>B$와 $A<B$가 정확히 반씩 나뉩니다.
4. 따라서 $A>B$인 경우 수는 $190$, 확률은 $190/400=19/40$입니다.

헷갈리기 쉬운 점

$1/2$가 아닌 이유는 같은 수를 고르는 경우가 있기 때문입니다.

7. 재혼 가정의 자녀 수

문제 한눈에 보기

자녀 총수는 12명, 남편과 유전적으로 연결된 자녀는 9명, 부인과 유전적으로 연결된 자녀도 9명일 때 재혼 후 태어난 자녀 수를 구합니다.

답

$6$

핵심 개념

남편 쪽, 부인 쪽, 둘 다인 자녀 수를 변수로 두고 연립방정식을 세우면 됩니다.

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

서술이 길어 보여도 결국 세 부류의 자녀 수를 세는 간단한 식 문제입니다.

단계별 풀이

1. 남편이 데려온 자녀를 $x$, 부인이 데려온 자녀를 $y$, 재혼 후 태어난 자녀를 $z$라 둡니다.
2. 전체 자녀 수는 $x+y+z=12$입니다.
3. 남편과 연결된 자녀는 $x+z=9$, 부인과 연결된 자녀는 $y+z=9$입니다.
4. 두 식을 빼면 $x=y$이고, 세 식을 합치면 $z=6$입니다.

헷갈리기 쉬운 점

재혼 후 자녀 $z$는 남편과 부인 양쪽 모두에 포함된다는 점이 핵심입니다.

8. 자동차 셔틀

문제 한눈에 보기

12명이 20km를 이동할 때 자동차를 셔틀처럼 써서 모두 동시에 도착하는 최소 시간을 구합니다.

답

2시간 36분

핵심 개념

세 그룹이 차를 타는 시간과 걷는 시간을 균형 있게 나누는 문제입니다.

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

한 그룹만 끝까지 태우면 다른 그룹이 너무 늦어져 전체 완료 시간이 최적이 되지 않습니다.

단계별 풀이

1. 12명을 4명씩 세 그룹으로 나눕니다.
2. 첫째, 둘째 그룹은 일정 시간 동안 차를 타고 나머지는 걷게 하면서 차가 돌아옵니다.
3. 동시에 도착 조건을 식으로 맞추면 앞의 두 그룹의 승차 시간은 같아야 하고, 총 시간은 $2.6$시간이 됩니다.
4. 따라서 최소 시간은 2시간 36분입니다.

헷갈리기 쉬운 점

빠른 차를 최대한 오래 태우는 것보다, 세 그룹의 도착 시각을 맞추는 것이 목표입니다.

9. 100개의 문

문제 한눈에 보기

1번부터 100번까지의 문을 번호의 배수인 사람마다 한 번씩 여닫을 때, 제시된 수 가운데 상태가 다른 문을 찾는 문제입니다.

답

$49$

핵심 개념

문은 약수 개수만큼 상태가 바뀌고, 약수 개수가 홀수인 수는 완전제곱수뿐입니다.

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

직접 시뮬레이션하지 않아도, 열린 문이 어떤 수인지 한 번에 판별할 수 있습니다.

단계별 풀이

1. 문 $n$은 $n$의 약수마다 한 번씩 토글됩니다.
2. 약수는 보통 짝을 이루므로 토글 횟수는 짝수입니다.
3. 완전제곱수만 가운데 약수가 하나 겹쳐 홀수 번 토글됩니다.
4. 보기 $2,5,7,49,72$ 중 완전제곱수는 $49$뿐입니다.

헷갈리기 쉬운 점

마지막에 열려 있는 문이 “특별한” 문입니다. 나머지는 모두 닫혀 있습니다.

10. 공 옮기기

문제 한눈에 보기

컵 A와 B 사이에서 공을 옮긴 뒤 A의 파란 공 수 $x$와 B의 빨간 공 수 $y$ 관계를 묻는 문제입니다.

답

$x=y$

핵심 개념

처음 B로 건너간 빨간 공과 다시 A로 돌아온 빨간 공 수를 비교하면 됩니다.

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

확률이 아니라 개수 보존만 따지는 문제라서, 식을 세우면 항상 같은 값이 나옵니다.

단계별 풀이

1. A에서 B로 빨간 공 $k$개를 옮깁니다.
2. 그중 B에 남은 빨간 공 수를 $y$라고 하면, k-y개는 다시 A로 돌아왔다는 뜻입니다.
3. A로 돌아온 공이 총 $k$개였으므로, 그 안의 파란 공 수는 $y$개입니다.
4. 따라서 A의 파란 공 수 $x$는 항상 $y$와 같습니다.

헷갈리기 쉬운 점

평균적으로 같다는 말이 아니라, 매번 정확히 같습니다.

11. 1, 2, 3 합 분해

문제 한눈에 보기

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

답

$81$

핵심 개념

마지막 항이 $1$, $2$, $3$인 경우로 나누면 점화식이 바로 나옵니다.

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

앞의 작은 값 결과를 재사용할 수 있는 전형적인 점화식 문제이기 때문입니다.

단계별 풀이

1. $f(n)$을 $n$을 $1,2,3$의 합으로 나타내는 방법 수라 두면
   $f(n)=f(n-1)+f(n-2)+f(n-3)$입니다.
2. 문제에서 $f(1)=1$, $f(2)=2$, $f(3)=4$를 줬습니다.
3. 차례로 계산하면 $f(4)=7$, $f(5)=13$, $f(6)=24$, $f(7)=44$, $f(8)=81$입니다.

헷갈리기 쉬운 점

$1+2+1$과 $2+1+1$은 순서가 다르므로 서로 다른 방법입니다.

12. 2×10 타일 채우기

문제 한눈에 보기

$1\times 2$ 타일로 $2\times 10$ 직사각형을 채우는 방법 수를 구하는 문제입니다.

답

$89$

핵심 개념

맨 왼쪽을 세로 타일 하나로 채우거나, 가로 타일 두 개로 채우는 두 경우로 나눕니다.

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

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

단계별 풀이

1. $g(n)$을 $2\times n$ 채우는 방법 수라 하면 $g(n)=g(n-1)+g(n-2)$입니다.
2. $g(1)=1$, $g(2)=2$입니다.
3. 피보나치처럼 계산하면 $g(10)=89$입니다.

헷갈리기 쉬운 점

가로 타일은 반드시 두 장이 한 쌍으로 들어가야 합니다.

13. 점 간격 맞추기

문제 한눈에 보기

첫 점은 고정한 채 나머지 6점을 움직여 7개의 점 간격을 모두 같게 만들고, 총 이동 거리 합을 최소화하는 문제입니다.

답

$34$

핵심 개념

등간격 목표를 $x_1,x_1+d,x_1+2d,\cdots$로 잡으면 총 이동 거리는 공차 $d$에 대한 절댓값 합 문제가 됩니다.

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

점들을 독립적으로 옮기는 문제가 아니라, 결국 “공차를 무엇으로 잡을 것인가”가 핵심 결정이기 때문입니다.

단계별 풀이

1. 첫 점이 고정되어 있으므로 목표 위치는 공차 $d$만 정하면 모두 결정됩니다.
2. 각 점의 이동 거리는 |현재 위치 - 목표 위치|이고, 총합은 이 값들의 합입니다.
3. 가능한 정수 $d$를 비교하면 공식 최솟값은 $34$입니다.

헷갈리기 쉬운 점

점마다 따로 최적을 잡는 것이 아니라, 모두 같은 간격이라는 한 조건을 동시에 만족해야 합니다.

14. 원형 자리배치

문제 한눈에 보기

8명의 친구를 원형 의자에 조건대로 배치하는 문제입니다.

답

A를 맨 위에 두면 시계 방향으로 C, F, B, D, E, H, G

핵심 개념

맞은편, 왼쪽 옆, 사이처럼 강한 조건부터 차례로 고정하면 됩니다.

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

자유롭게 앉히기 시작하면 경우가 많아 보이지만, 실제로는 강제되는 자리가 많습니다.

단계별 풀이

1. A 맞은편에 D를 둡니다.
2. E는 D의 왼쪽 옆이므로 함께 묶입니다.
3. H는 G와 E 사이에 와야 하므로 E-H-G 덩어리가 생깁니다.
4. G와 C 사이에 한 사람이 있어야 하고, F는 A, D 옆에 올 수 없으므로 나머지를 채우면 공식 배치가 나옵니다.

헷갈리기 쉬운 점

원형에서는 회전만 같은 배치라고 생각하기 쉽지만, 이 문제는 A 자리가 이미 고정되어 있습니다.

15. 바람막이 설치

문제 한눈에 보기

길이 5 구간을 덮는 바람막이로 채소가 있는 이랑을 모두 덮는 최소 개수를 구하는 문제입니다.

답

$5$

핵심 개념

가장 왼쪽의 미덮임 채소를 기준으로 가능한 한 오른쪽까지 덮는 greedy가 통합니다.

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

같은 개수의 바람막이로 덮는 범위를 최대화하려면 매번 가장 멀리 보내는 선택이 유리합니다.

단계별 풀이

1. 아직 안 덮인 가장 왼쪽 채소를 찾습니다.
2. 그 채소를 포함하면서 가장 오른쪽까지 덮는 폭 5 구간을 놓습니다.
3. 이를 반복하면 공식 정답처럼 $5$개로 모든 채소 이랑을 덮을 수 있습니다.

헷갈리기 쉬운 점

한가운데만 고르는 문제가 아니라, 좌우로 실제 덮이는 길이 5 전체를 보고 판단해야 합니다.

16. 창고 재배치

문제 한눈에 보기

기존에는 5개 창고에, 새로는 6개 창고에 고객 물건을 순환 배치할 때 옮길 필요가 없는 고객 수를 구합니다.

답

$14$

핵심 개념

고객 번호 $n$에 대해 옛 창고 번호와 새 창고 번호가 같아지는 조건을 나머지로 세면 됩니다.

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

한 명씩 써 보기보다 $\mathrm{mod}5$, $\mathrm{mod}6$ 조건으로 바꾸면 패턴이 30명마다 반복됩니다.

단계별 풀이

1. 고객 번호를 $n$이라 하면 옛 창고는 $((n-1)\mathrm{mod}5)+1$, 새 창고는 $((n-1)\mathrm{mod}6)+1$입니다.
2. 두 값이 같으려면 $n-1$을 $5$와 $6$으로 나눈 나머지가 둘 다 $0,1,2,3,4$ 중 같은 값이어야 합니다.
3. 이 패턴은 $\mathrm{lcm}(5,6)=30$명마다 반복되고, 30명당 일치하는 고객은 5명입니다.
4. 64명은 $30+30+4$로 볼 수 있으므로 $5+5+4=14$명입니다.

헷갈리기 쉬운 점

새 창고 번호의 나머지 $5$는 창고 6을 뜻하므로, 옛 창고와 절대 같아질 수 없습니다.

17. 하노이 탑 모양 바꾸기

문제 한눈에 보기

세 막대의 원판 배치를 주어진 목표 모양으로 바꾸는 문제입니다. 최소 횟수 조건은 없습니다.

답

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

핵심 개념

큰 원판부터 목표 위치를 정하고, 그 위를 막는 작은 원판들을 보조 막대로 잠시 옮기는 하노이 탑 전략을 쓰면 됩니다.

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

큰 원판은 작은 원판 위로 갈 수 없으므로, 결국 큰 원판의 자리부터 해결해야 전체 배치가 맞습니다.

단계별 풀이

1. 목표 상태에서 가장 큰 원판이 가야 할 막대를 먼저 확인합니다.
2. 그 원판 위의 작은 원판들을 다른 막대로 잠시 옮깁니다.
3. 큰 원판을 목표 위치에 놓은 뒤, 나머지 작은 원판들도 같은 방식으로 재귀적으로 정리합니다.
4. 최소 횟수 조건이 없으므로, 목표 모양만 맞추면 정답입니다.

헷갈리기 쉬운 점

정답은 “몇 번”이 아니라 “어떤 최종 배치인가”입니다.

18. 선물 경로 최대화

문제 한눈에 보기

A와 B가 격자 위를 내려오며 선물을 모을 때, 두 사람이 지나가는 칸이 최대 하나만 겹치도록 하면서 총합을 최대화하는 문제입니다.

답

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

핵심 개념

두 경로가 거의 겹치지 않는 최대합 경로 문제이므로, 네 방향 DP를 합쳐 생각하면 됩니다.

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

한 사람만 최대로 보내면 다른 사람 경로가 망가질 수 있으므로, 두 경로를 동시에 봐야 합니다.

단계별 풀이

1. A는 좌상단에서 우하단으로, B는 우상단에서 좌하단으로 움직입니다.
2. 각 칸까지의 최댓값을 네 방향에서 미리 구해 두면, 두 경로가 만나는 형태를 비교할 수 있습니다.
3. 공식 정답 화면의 최적 총합은 $137$이고, 그중 A가 $65$, B가 $72$를 가져갑니다.

헷갈리기 쉬운 점

두 사람이 같은 칸을 여러 번 겹칠 수 있는 것이 아니라, 최대 한 칸만 겹칠 수 있습니다.

19. 가장 작은 수 만들기

문제 한눈에 보기

숫자 블록을 순서대로 꺼내 양끝에 붙여 만들 수 있는 가장 작은 수를 찾는 문제입니다.

답

$1344968746$

핵심 개념

앞자리를 더 작게 만드는 선택이 전체 수를 가장 크게 좌우합니다.

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

같은 숫자를 뒤에서 줄이는 것보다, 맨 앞 몇 자리를 더 작게 만드는 것이 훨씬 중요합니다.

단계별 풀이

1. 블록을 하나씩 보며 왼쪽 끝과 오른쪽 끝 중 어디에 붙일지 결정합니다.
2. 현재까지 만든 수의 접두사가 더 작아지는 쪽을 우선합니다.
3. 공식 정답 결과는 $1344968746$입니다.

헷갈리기 쉬운 점

지금 보이는 한 자리만 비교하면 안 되고, 그 선택이 전체 앞부분을 어떻게 바꾸는지 봐야 합니다.

20. 숨은 순열 찾기

문제 한눈에 보기

원소 두 개를 바꿀 때마다 “차이의 합”을 알려 주는 장치를 이용해 숨겨진 순열을 복원하는 문제입니다.

답

4 3 7 1 9 8 5 6 10 2 11

핵심 개념

교환 전후 오차 총합의 변화량은 바꾼 두 위치의 실제 값 정보를 직접 드러냅니다.

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

순열을 직접 볼 수는 없지만, 총 오차 변화는 충분히 강한 정보라서 위치별 값을 추적할 수 있습니다.

단계별 풀이

1. 시작 순열을 정하고 서로 다른 두 칸을 골라 바꿔 봅니다.
2. 차이의 합이 얼마나 줄거나 늘었는지를 보고, 그 두 칸의 실제 값 후보를 좁힙니다.
3. 이런 비교를 반복하면 각 칸 값을 차례로 확정할 수 있습니다.
4. 공식 정답 화면의 최종 순열은 4 3 7 1 9 8 5 6 10 2 11입니다.

헷갈리기 쉬운 점

한 번의 교환이 바꾸는 정보는 두 칸뿐이므로, 변화량을 두 위치의 비교 문제로 해석해야 합니다.

개념 한눈에 보기

주제	해당 문제	한 줄 요약
수론과 나머지	1, 9	소수 성질과 완전제곱수 판정을 이용하면 큰 계산을 피할 수 있다.
경우의 수와 확률	2, 6	종료 시점 분류와 대칭을 이용하면 짧게 계산된다.
DP와 점화식	11, 12, 18	마지막 선택이나 진행 방향으로 나누면 작은 문제 재사용이 가능하다.
논리와 보존량	3, 5, 10	숫자 조건과 참거짓, 공 개수 보존이 답을 고정한다.
최적화	8, 13, 15, 16	셔틀 시간, 공차, greedy, 나머지 패턴을 함께 봐야 최소가 나온다.
구성형	14, 17, 19, 20	조건을 만족하는 정답 배치를 만들고, 왜 가능한지 설명할 수 있어야 한다.