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

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

이 문서는 2023 - 초등부 기출문제를 바탕으로, 정답 자료를 초등학생도 따라갈 수 있게 학습용 풀이로 다시 쓴 문서입니다.

1. 자율주행

문제 한눈에 보기

왼쪽 차를 보면서, 자기 속도가 더 빠르면 그 차와 같은 속도로 낮춥니다. 마지막에 남는 서로 다른 속도의 개수를 묻는 문제입니다.

답

$6$

핵심 개념

왼쪽부터 보면서 지금까지 나온 가장 작은 값만 기억하면 됩니다.

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

각 자동차는 바로 왼쪽 자동차보다 빨라지지 못합니다. 그래서 뒤로 갈수록 속도는 그대로이거나 더 작아집니다.

단계별 풀이

1. 처음 속도는 $18,15,18,13,12,13,6,15,1$입니다.
2. 왼쪽부터 보면 최종 속도는 이렇게 됩니다.
3. $18$
4. $15$는 왼쪽보다 느리니 그대로 갑니다.
5. 다음 $18$은 왼쪽 $15$보다 빠르니 $15$가 됩니다.
6. $13$은 그대로, $12$도 그대로 갑니다.
7. 다음 $13$은 왼쪽 $12$보다 빠르니 $12$가 됩니다.
8. $6$은 그대로 갑니다.
9. 다음 $15$는 왼쪽 $6$보다 빠르니 $6$이 됩니다.
10. 마지막 $1$은 그대로 갑니다.
11. 최종 속도는 $18,15,15,13,12,12,6,6,1$입니다.
12. 서로 다른 속도는 $18,15,13,12,6,1$의 6가지입니다.

헷갈리기 쉬운 점

바로 왼쪽 차만 보면 되지만, 그 왼쪽 차도 이미 느려졌을 수 있습니다. 그래서 실제로는 왼쪽부터의 최솟값을 따라가게 됩니다.

2. 양팔 저울

문제 한눈에 보기

추 $2$kg, $5$kg, $8$kg을 양쪽에 놓아 물통의 무게를 만들 수 있을 때, 15kg 이하에서 만들 수 없는 무게를 찾는 문제입니다.

답

$12$kg

핵심 개념

양팔저울에서는 한쪽에 올리는 것이 아니라 두 쪽 차이를 만드는 문제로 봐야 합니다.

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

추를 물통 쪽에도 놓을 수 있고 반대쪽에도 놓을 수 있습니다. 그래서 가능한 무게는 $|\pm 2\pm 5\pm 8|$처럼 생각할 수 있습니다.

단계별 풀이

1. 만들 수 있는 대표 무게를 적어 봅니다.
2. $1=8-5-2$
3. $6=8-2$
4. $11=8+5-2$
5. 그 밖에도 $2,3,5,7,8,10,13,15$ 등을 만들 수 있습니다.
6. 가능한 값을 쭉 모아 보면 $12$는 나오지 않습니다.
7. 따라서 만들 수 없는 무게는 $12$kg입니다.

헷갈리기 쉬운 점

$8+5-2=11$처럼 생각해야 합니다. 그냥 더하기만 하면 양팔저울의 특징을 놓치게 됩니다.

3. 거짓말

문제 한눈에 보기

네 학생 중 한 명이 창문을 깼고, 거짓말을 할 수도 있는 학생은 한 명뿐입니다. 누가 창문을 깼는지 찾는 문제입니다.

답

D

핵심 개념

조건이 적을 때는 하나를 가정해 보고 모순이 생기는지 확인하면 좋습니다.

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

말이 네 개뿐이라 모든 경우를 길게 셀 필요가 없습니다. 한 사람씩 범인이라고 생각해 보면 금방 모순이 드러납니다.

단계별 풀이

1. D가 범인이 아니라고 가정해 봅시다.
2. 그러면 C의 말 D가 깼어요는 거짓이 됩니다.
3. D의 말 C는 거짓말 중은 참이 됩니다.
4. B의 말 A 또는 D에서 D는 아니니 A가 범인이어야 합니다.
5. 그런데 A는 저는 안 깼어요라고 했으니 이것도 거짓이 됩니다.
6. 이렇게 되면 C와 A, 두 명이 거짓말쟁이가 됩니다.
7. 문제에서는 거짓말할 수 있는 사람이 한 명뿐이라 모순입니다.
8. 따라서 D가 범인입니다.
9. 실제로 D가 범인이라면 A의 말은 참, B의 말도 참, C의 말도 참, D의 말만 거짓이어서 조건과 딱 맞습니다.

헷갈리기 쉬운 점

한 명만 거짓말할 수도 있다는 말은 딱 한 명만 거짓이 될 수 있다는 뜻으로 써야 합니다.

4. 봉투

문제 한눈에 보기

처음 봉투의 돈은 $9,3,4,5,8$장입니다. 봉투를 쪼갤 수는 있지만 서로 합칠 수는 없습니다. 어느 봉투도 다른 봉투의 2배 이상이 되지 않게 하려면 최소 몇 봉투가 필요한지 묻습니다.

답

$7$

핵심 개념

가장 작은 봉투 금액을 먼저 생각하면, 나머지 봉투가 가질 수 있는 범위가 정해집니다.

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

조건이 2배 이상 금지이므로 제일 작은 봉투가 정해지면 제일 큰 봉투의 한계도 같이 정해집니다.

단계별 풀이

1. 처음에 $3$이 있는 봉투가 있으므로 가장 작은 봉투는 3보다 클 수 없습니다.
2. 가장 작은 봉투가 3이면, 모든 봉투는 $3,4,5$ 중 하나여야 합니다.
3. $9$는 한 봉투로 둘 수 없으니 $4+5$처럼 둘로 나눠야 합니다.
4. $8$도 한 봉투로 둘 수 없으니 $3+5$ 또는 $4+4$처럼 둘로 나눠야 합니다.
5. $3$, $4$, $5$는 그대로 둘 수 있습니다.
6. 그래서 필요한 봉투 수는 $1(3)+1(4)+1(5)+2(8)+2(9)=7$개입니다.
7. 예를 들어 $3,4,5,3,5,4,5$처럼 만들 수 있습니다.

헷갈리기 쉬운 점

이 문제는 쪼개기만 가능하고 합치기는 불가능합니다. 그래서 전체 돈 29를 그냥 아무렇게나 다시 나누는 문제로 보면 안 됩니다.

5. 시험 채점

문제 한눈에 보기

4명이 서로 시험지를 바꿔 채점할 때, 아무도 자기 시험지를 채점하지 않게 하는 방법 수를 묻습니다.

답

$9$

핵심 개념

한 사람의 선택을 먼저 정하고, 그다음 경우를 작은 문제로 나누면 세기 쉬워집니다.

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

4명을 한꺼번에 세면 헷갈립니다. 학생 1이 누구 시험지를 잡는지만 먼저 정하면 나머지가 작아집니다.

단계별 풀이

1. 학생 1은 자기 것만 빼고 $2,3,4$ 중 하나를 고를 수 있으니 3가지 출발이 있습니다.
2. 예를 들어 학생 1이 학생 2의 시험지를 잡았다고 합시다.
3. 이때 학생 2가 학생 1의 시험지를 잡으면, 학생 3과 4는 서로 바꾸는 1가지밖에 없습니다.
4. 학생 2가 학생 1의 시험지를 잡지 않으면, 남은 3명이 빙글 도는 3-cycle이 되고 이 경우는 2가지입니다.
5. 그래서 학생 1이 $2$를 고른 경우는 $1+2=3$가지입니다.
6. 학생 1이 $3$을 고르거나 $4$를 고르는 경우도 똑같이 3가지씩입니다.
7. 따라서 전체는 $3+3+3=9$가지입니다.

헷갈리기 쉬운 점

누가 누구 것을 채점하는지는 순서가 있는 배치입니다. 그냥 짝만 만드는 문제가 아닙니다.

6. ABAB

문제 한눈에 보기

문자열 bababbaaba를 $a$, $b$, ab, ba만 사용해서 나눌 때, 조각 수를 가장 적게 만드는 문제입니다.

답

$6$

핵심 개념

조각 수를 줄이려면 가능한 한 길이 2짜리 조각을 많이 써야 합니다.

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

문자열 길이는 10입니다. 조각 수를 최소로 하려면 한 조각이 두 글자인 ab나 ba를 많이 써야 유리합니다.

단계별 풀이

1. 만약 5조각으로 나누려면 모든 조각이 길이 2여야 합니다.
2. 그러면 문자열을 두 글자씩 끊었을 때 ba | ba | bb | aa | ba가 됩니다.
3. 그런데 bb와 aa는 사용할 수 없습니다.
4. 그래서 5조각은 불가능합니다.
5. 6조각은 가능합니다.
6. 예를 들어 ba | ba | b | ba | ab | a로 나누면 됩니다.
7. 따라서 최소 조각 수는 6입니다.

헷갈리기 쉬운 점

ab, ba는 쓸 수 있지만 aa, bb는 안 됩니다. 이 차이를 놓치면 5조각이라고 착각하기 쉽습니다.

7. 이진 문자열

문제 한눈에 보기

$0001011$을 $1010010$으로 바꿀 때, 할 수 있는 일은 이웃한 두 글자를 바꾸는 것뿐입니다. 최소 몇 번 바꿔야 하는지 묻습니다.

답

$7$

핵심 개념

이웃한 자리 바꾸기는 $1$들이 자기 목표 자리까지 몇 칸 움직여야 하는지 세면 됩니다.

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

0과 1이 섞인 문자열에서 이웃 교환 횟수는, 같은 종류의 글자들이 움직인 거리의 합으로 계산할 수 있습니다.

단계별 풀이

1. 처음 문자열에서 $1$의 위치는 $4,6,7$번째입니다.
2. 목표 문자열에서 $1$의 위치는 $1,3,6$번째입니다.
3. 첫 번째 $1$은 $4$에서 $1$로 가야 하니 3칸 움직입니다.
4. 두 번째 $1$은 $6$에서 $3$으로 가야 하니 3칸 움직입니다.
5. 세 번째 $1$은 $7$에서 $6$으로 가야 하니 1칸 움직입니다.
6. 모두 더하면 $3+3+1=7$입니다.

헷갈리기 쉬운 점

$1$들을 서로 구별해서, 첫 번째 $1$은 첫 번째 목표 자리로 보내야 합니다. 그래야 가장 적게 움직입니다.

8. 양말

문제 한눈에 보기

어두운 방에서 양말을 꺼낼 때, 최악의 경우에도 10켤레를 만들 수 있으려면 최소 몇 짝을 꺼내야 하는지 묻습니다.

답

$23$

핵심 개념

이런 문제는 최악의 경우를 일부러 만든다고 생각하면 쉽습니다.

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

바로 10켤레를 세지 말고, 10켤레가 아직 안 생기도록 최대한 버티는 경우를 생각해야 합니다.

단계별 풀이

1. 색은 빨강, 초록, 파랑, 검정 4가지입니다.
2. 먼저 각 색 하나씩만 꺼내면 4짝인데 아직 한 켤레도 없습니다.
3. 이제 양말을 더 꺼내면, 같은 색이 나올 때마다 켤레 수가 늘어납니다.
4. 9켤레까지만 만들면서 최대한 많이 꺼내려면, 각 색마다 짝 하나 없는 양말을 하나씩 남기면 됩니다.
5. 9켤레는 양말 $18$짝입니다.
6. 여기에 남은 외톨이 4짝을 더하면 $22$짝까지는 9켤레일 수 있습니다.
7. 한 짝을 더 꺼내면 반드시 10번째 켤레가 생깁니다.
8. 따라서 답은 23짝입니다.

헷갈리기 쉬운 점

양말 개수가 아주 많아도 색 종류는 4개뿐입니다. 최악의 경우를 만드는 핵심은 색 종류 수입니다.

9. 가전제품 교체

문제 한눈에 보기

콘센트 구멍은 4개뿐인데, 정해진 순서대로 18번 기기를 써야 합니다. 교체 횟수를 최소로 만드는 문제입니다.

답

$8$

핵심 개념

앞으로 가장 늦게 다시 쓸 물건, 또는 다시 안 쓸 물건을 빼는 것이 가장 유리합니다.

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

지금 당장 덜 중요한 것이 아니라 앞으로 오래 안 쓸 것을 빼야, 나중에 다시 꽂는 횟수를 줄일 수 있습니다.

단계별 풀이

1. 처음에는 $(1,2,3,4)$가 꽂혀 있습니다.
2. $5$를 써야 할 때, 앞으로 다시 가장 늦게 나오는 것은 $2$이므로 $2$를 뽑습니다.
3. $6$을 써야 할 때는 앞으로 가장 늦은 $5$를 뽑습니다.
4. $7$을 써야 할 때는 앞으로 가장 늦은 $3$을 뽑습니다.
5. $4,1,6$은 이미 꽂혀 있으니 그대로 씁니다.
6. $3$이 다시 필요할 때는 이제 앞으로 안 쓰는 $4$를 뽑습니다.
7. $8$이 필요할 때는 현재 꽂힌 것 중 앞으로 가장 늦게 다시 쓰는 $3$을 뽑습니다.
8. 그 뒤 $5$, $2$, $3$이 필요할 때도 같은 규칙을 반복하면 총 교체 횟수는 8번이 됩니다.

헷갈리기 쉬운 점

지금 바로 안 쓰는 것과 앞으로 가장 늦게 쓰는 것은 다를 수 있습니다. 이 문제는 미래를 보고 빼기가 핵심입니다.

10. 근무 계획

문제 한눈에 보기

작업마다 이득과 마감일이 있고, 기계는 2대라서 하루에 작업 2개까지 할 수 있습니다. 4일 동안 최대 이득을 구합니다.

답

$211$

핵심 개념

이득이 큰 작업부터 보고, 가능한 가장 늦은 날에 넣는 그리디 방법을 쓰면 됩니다.

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

값이 큰 작업은 최대한 살리고, 마감일이 이른 칸은 나중을 위해 아껴야 전체 합이 커집니다.

단계별 풀이

1. 하루에 2개씩 할 수 있으니 전체 자리는 $8$칸입니다.
2. 이득이 큰 작업부터 차례로 봅니다.
3. 선택되는 작업은 $1,2,3,4,5,7,9,10$번입니다.
4. 이 작업들의 이득 합은 $40+35+30+29+25+20+16+16=211$입니다.
5. 예를 들어 이렇게 배치할 수 있습니다.
6. 1일차: $3,5$
7. 2일차: $1,2$
8. 3일차: $4,9$
9. 4일차: $7,10$
10. 모든 작업이 마감일 안에 끝나므로 이득 211이 가능합니다.

헷갈리기 쉬운 점

기계가 2대라는 말은 하루 자리 2칸으로 바꿔서 생각해야 합니다.

11. 비트 카운터

문제 한눈에 보기

10비트 수가 $0000000000$에서 $1111111111$까지 1씩 증가할 때, 비트가 바뀐 총 횟수를 구하는 문제입니다.

답

$2036$

핵심 개념

각 비트가 몇 번 켜지고 꺼지는지를 따로 세면 됩니다.

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

매번 전체를 직접 세면 너무 많습니다. 하지만 각 자리의 규칙은 아주 일정하게 반복됩니다.

단계별 풀이

1. 맨 오른쪽 비트는 1씩 증가할 때마다 바뀝니다.
2. 그래서 첫째 비트는 $1023$번 바뀝니다.
3. 둘째 비트는 2번에 한 번 바뀌니 $511$번 바뀝니다.
4. 셋째 비트는 $255$번, 그다음은 $127,63,31,15,7,3,1$번 바뀝니다.
5. 모두 더하면
6. $1023+511+255+127+63+31+15+7+3+1=2036$
7. 따라서 답은 2036입니다.

헷갈리기 쉬운 점

상태 개수는 1024개지만, 상태가 바뀌는 횟수는 $1023$번입니다.

12. 분수 트리

문제 한눈에 보기

루트 $1/1$에서 시작하는 분수 트리에서 $29/67$까지 가는 길을 L, R로 써야 합니다.

답

RLLLLRRRLL

핵심 개념

앞으로 가기보다 거꾸로 부모를 찾는 것이 훨씬 쉽습니다.

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

앞으로 내려가면 갈림길이 계속 생깁니다. 하지만 거꾸로 올라가면 매번 부모가 하나로 정해집니다.

단계별 풀이

1. $29/67$은 분모가 더 크니 마지막 이동은 L입니다.
2. 왼쪽 자식 $p/(p+q)$의 부모는 $p/(q-p)$이므로 부모는 $29/38$입니다.
3. $29/38$도 분모가 더 크니 또 L, 부모는 $29/9$입니다.
4. 이제 $29/9$는 분자가 더 크니 마지막 이동은 R입니다.
5. 오른쪽 자식 $(p+q)/q$의 부모는 $(p-q)/q$이므로 $20/9$, $11/9$, $2/9$로 올라갑니다.
6. 다시 분모가 더 크므로 $2/7$, $2/5$, $2/3$, $2/1$로 올라갑니다.
7. $2/1$의 부모는 $1/1$입니다.
8. 거꾸로 모은 글자를 뒤집으면 RLLLLRRRLL이 됩니다.

헷갈리기 쉬운 점

거꾸로 올라갈 때 만든 L, R은 마지막에 반드시 뒤집어야 합니다.

13. 얽힌 그래프

문제 한눈에 보기

점들을 움직여서 빨간 교차선이 없어지게 만들면 됩니다.

답

정답은 한 가지가 아닙니다. 예를 들어 6개 점이 육각형처럼 둘러서도록 배치하면 됩니다.

핵심 개념

선이 교차하는 이유는 점의 순서가 꼬였기 때문입니다.

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

선 자체를 바꿀 수는 없습니다. 바꿀 수 있는 건 점의 위치뿐이므로, 점들의 둘레 순서를 바꾸는 데 집중해야 합니다.

단계별 풀이

1. 바깥 네 점만 보면 큰 사각형입니다.
2. 안쪽 두 점이 사각형의 한가운데에 있어서 빨간 선이 서로 가로질러 만납니다.
3. 그래서 안쪽 두 점을 그대로 두지 말고, 둘레 쪽으로 빼면 됩니다.
4. 왼쪽 안쪽 점은 왼쪽 위와 왼쪽 아래 사이 쪽으로, 오른쪽 안쪽 점은 오른쪽 위와 오른쪽 아래 사이 쪽으로 옮깁니다.
5. 그러면 6개 점이 육각형 둘레 순서처럼 놓이게 됩니다.
6. 이렇게 되면 빨간 선끼리 만나지 않게 만들 수 있습니다.

헷갈리기 쉬운 점

이 문제는 정답 좌표 하나를 찾는 문제가 아닙니다. 교차만 없애면 됩니다.

14. 원판 배치하기

문제 한눈에 보기

원판 7개를 점 7개 위에 놓되, 이웃한 원판끼리 딱 맞닿게 배치하는 문제입니다.

답

한 가지 정답 예시는 그림 아래쪽처럼, 왼쪽부터 파란색 - 초록색 - 빨간색 - 하늘색 - 보라색 - 회색 - 주황색입니다.

핵심 개념

이웃 두 원판이 외접한다는 말은 두 반지름의 합 = 두 점 사이 거리라는 뜻입니다.

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

색이나 모양보다 중요한 것은 크기 합입니다. 어떤 두 원판이 이웃해야 하는지가 이 합으로 결정됩니다.

단계별 풀이

1. 각 점 사이 거리는 고정되어 있습니다.
2. 이웃한 두 원판은 그 거리만큼 반지름 합이 맞아야 합니다.
3. 그래서 큰 원판은 큰 간격 옆에, 작은 원판은 작은 간격 옆에 오게 됩니다.
4. 아래 예시 배치를 보면 큰 빨간 원판이 넓은 간격을 맡고, 아주 작은 회색 원판은 좁은 간격을 맡습니다.
5. 이처럼 간격과 반지름 합을 맞추면 조건을 만족하는 배치를 만들 수 있습니다.

헷갈리기 쉬운 점

원판 중심은 반드시 점 위에 있어야 합니다. 원판 모양이 겹치지 않는지만 보면 안 됩니다.

15. 감마선

문제 한눈에 보기

뚜껑은 왼쪽으로만 움직일 수 있습니다. 최종적으로 뚜껑이 덮는 보물 가치 합을 최대로 만들어야 합니다.

답

최대 합은 $306$이고, 한 가지 최적 배치는 $1,3,4,5,8,9$번째 칸을 덮는 것입니다.

핵심 개념

왼쪽으로만 움직일 수 있으니, 각 뚜껑은 자기보다 왼쪽 어딘가만 맡을 수 있습니다.

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

마음대로 순간이동할 수 있으면 가장 큰 값만 고르면 되지만, 이 문제는 왼쪽으로만 움직이는 제한이 있어서 순서를 지켜야 합니다.

단계별 풀이

1. 처음 뚜껑 위치를 왼쪽부터 보면 $2,5,7,9,11,12$번째입니다.
2. 첫 번째 뚜껑은 $1$ 또는 $2$까지만 갈 수 있습니다.
3. 이런 식으로 각 뚜껑이 갈 수 있는 범위 안에서 값이 큰 칸을 고르면 됩니다.
4. 최적으로 고르면 $1,3,4,5,8,9$번째 칸을 덮을 수 있습니다.
5. 그 값은 $39,53,59,49,55,51$입니다.
6. 합은 $39+53+59+49+55+51=306$입니다.

헷갈리기 쉬운 점

값이 큰 칸이 있어도, 너무 오른쪽이면 어떤 뚜껑도 못 갈 수 있습니다. 값과 도달 가능 범위를 같이 봐야 합니다.

16. 집 위치

문제 한눈에 보기

첫 번째 카메라는 0에 있습니다. 각 집은 0에서 왼쪽 또는 오른쪽에 있을 수 있고, 두 번째 카메라 위치까지 함께 맞춰야 합니다.

답

한 가지 정답은 두 번째 카메라 = 38이고, 집의 위치는 다음과 같습니다.

1: 52   2: -53  3: 79   4: 10   5: 87
6: -20  7: 44   8: -75  9: -54  10: -1
11: -60 12: 20  13: 66  14: -5  15: 50
16: -46 17: 96  18: 31  19: -16 20: -100

모든 부호를 반대로 바꾸고 두 번째 카메라를 $-38$에 두는 거울 대칭 해도 됩니다.

핵심 개념

각 집은 먼저 $+a$ 또는 $-a$ 두 후보만 있습니다. 그다음 두 번째 카메라 거리로 하나를 골라냅니다.

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

첫 카메라 정보만 보면 집 위치는 양쪽 두 후보뿐입니다. 그래서 문제는 사실 왼쪽인지 오른쪽인지를 정하는 퍼즐입니다.

단계별 풀이

1. 예를 들어 1번 집은 첫 카메라에서 52만큼 떨어져 있으니 후보가 $52$와 $-52$입니다.
2. 두 번째 카메라와의 거리가 14여야 하므로, 두 번째 카메라 위치 $x$는 $38,66,-38,-66$ 중 하나여야 합니다.
3. 4번 집은 후보가 $10,-10$이고 두 번째 거리 28이므로 $x$는 $38,-38,18,-18$ 중 하나입니다.
4. 두 집을 함께 만족시키는 값은 $38$ 또는 $-38$뿐입니다.
5. 이제 $x=38$이라고 정하면, 각 집마다 $+a$, $-a$ 중 둘째 거리까지 맞는 쪽이 딱 하나씩 정해집니다.
6. 그 결과 위 표와 같은 위치가 나옵니다.

헷갈리기 쉬운 점

두 번째 카메라는 채점 요소가 아니지만, 답을 찾는 데는 아주 좋은 힌트입니다.

17. 2층

문제 한눈에 보기

같은 열의 위아래 숫자만 바꿀 수 있습니다. 원래 표와는 달라야 하고, 두 행 모두 중복 없는 표가 되게 하려면 최소 몇 번 바꿔야 하는지 묻습니다.

답

최소 $5$번이고, $4,8,12,13,15$번째 열을 바꾸면 됩니다.

핵심 개념

바꾼 열들의 윗줄 숫자 모음과 아랫줄 숫자 모음이 서로 같아야, 바꾼 뒤에도 중복이 생기지 않습니다.

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

한 열만 바꾸면 위줄은 숫자 하나를 잃고 다른 숫자 하나를 얻습니다. 그래서 여러 열을 묶어 빙글 도는 순환을 만들어야 안전합니다.

단계별 풀이

1. 각 열을 윗숫자 -> 아랫숫자로 생각해 봅니다.
2. 그러면 숫자들이 서로 이어지는 순환이 생깁니다.
3. 이 문제의 순환은 길이 10짜리 하나와 길이 5짜리 하나가 나옵니다.
4. 가장 적게 바꾸려면 더 짧은 순환 하나만 고르면 됩니다.
5. 짧은 순환은 $1\to 10\to 4\to 11\to 5\to 1$입니다.
6. 이 숫자들이 있는 열이 $4,8,12,13,15$번째 열입니다.
7. 이 다섯 열을 바꾸면 그림 아래 예시처럼 두 줄 모두 중복 없는 상태가 됩니다.

헷갈리기 쉬운 점

원래 표도 이미 중복이 없지만, 문제에서 원래 표와 달라야 한다고 했으니 최소 1번 이상은 바꿔야 합니다.

18. 합이 0

문제 한눈에 보기

수열을 여러 부분으로 나눌 때, 맨 앞과 맨 뒤를 제외한 모든 부분의 합이 0이 되게 하면서, 합이 0인 부분 수를 최대화하는 문제입니다.

답

최대 $3$개

핵심 개념

어떤 구간 합이 0이라는 말은 앞에서부터의 누적합이 같은 값으로 두 번 나온다는 뜻입니다.

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

부분합을 매번 새로 더하면 느리고 헷갈립니다. 누적합을 보면 0이 되는 구간을 한눈에 찾을 수 있습니다.

단계별 풀이

1. 수열은 $7,-5,2,-4,1,6,-3,-4,4,-3,1,5,-3,-3$입니다.
2. 한 가지 최적 분할은 다음과 같습니다.
3. $[7,-5,2]|[-4,1,6,-3]|[-4,4]|[-3,1,5,-3]|[-3]$
4. 각 부분의 합은 $4,0,0,0,-3$입니다.
5. 가운데 세 부분이 모두 0이므로 조건을 만족합니다.
6. 그리고 0이 되는 부분 수는 3개입니다.
7. 이보다 더 많이 만들 수는 없습니다.

헷갈리기 쉬운 점

앞부분과 뒷부분만 0이 아니어도 됩니다. 하지만 그 사이에 있는 부분은 전부 0이어야 합니다.

19. Max-plus tree

문제 한눈에 보기

리프 16칸에 숫자 1부터 16까지를 한 번씩 배치해서 루트 값을 최대로 만드는 문제입니다.

답

루트의 최댓값은 $81$입니다. 한 가지 최적 배치는 왼쪽 리프부터

$1,2,11,3,12,13,4,5,6,7,8,9,14,15,10,16$

입니다.

핵심 개념

plus는 두 자식을 모두 더하지만, max는 둘 중 큰 쪽 하나만 봅니다.

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

큰 수를 아무 데나 두면 낭비될 수 있습니다. max에서 지는 쪽에 큰 수를 많이 놓으면 손해입니다.

단계별 풀이

1. 루트는 plus이므로 왼쪽 큰 덩어리와 오른쪽 큰 덩어리를 둘 다 키워야 합니다.
2. 오른쪽 덩어리는 마지막에 $16$이 무조건 더해지고, 그 앞의 $plus(13,14)$ 쪽도 둘 다 살아남습니다.
3. 그래서 큰 수 $14,15,16$을 오른쪽 깊은 plus 쪽에 두는 것이 좋습니다.
4. 왼쪽 큰 덩어리는 중간에 max가 많아서, 결국 이기는 가지에 있는 수만 많이 반영됩니다.
5. 그래서 $11,12,13$ 같은 큰 수는 왼쪽에서 plus로 더해지는 한 줄에 모아 두는 것이 유리합니다.
6. 그림 예시 배치를 넣으면 내부 값이 차례로 커져서 루트 값이 $81$이 됩니다.

헷갈리기 쉬운 점

max 아래에서는 두 가지를 모두 키울 필요가 없습니다. 결국 더 큰 쪽 하나만 위로 올라갑니다.

20. 벌집 채우기

문제 한눈에 보기

처음 몇 칸만 칠한 뒤, 주변 6칸 중 3칸 이상이 칠해지면 나도 칠해진다 규칙으로 결국 전체가 다 칠해지게 해야 합니다.

답

최소 칸 수는 $9$이고, 위 그림처럼 9칸을 먼저 칠하면 됩니다.

핵심 개념

새 칸이 칠해지려면 주변에 이미 3칸이 필요합니다. 그래서 퍼져 나갈 씨앗을 삼각형처럼 겹치게 놓아야 합니다.

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

아무 데나 9칸을 찍으면 퍼지지 않습니다. 가운데에서 시작해 이웃 관계가 이어지게 놓아야 연쇄 반응이 일어납니다.

단계별 풀이

1. PDF 마지막 페이지에 최소값이 $m=9$라고 주어져 있습니다.
2. 따라서 9칸으로 성공하는 배치 하나만 찾으면 그것이 최적입니다.
3. 정답 예시는 위쪽 대각선에 4칸, 아래쪽 띄엄띄엄 줄에 5칸을 두는 모양입니다.
4. 이렇게 두면 가운데 칸들이 먼저 이웃 3칸 조건을 채웁니다.
5. 가운데가 채워지면 그다음 줄도 같은 이유로 채워집니다.
6. 이 연쇄가 바깥쪽까지 번져서 결국 모든 칸이 칠해집니다.
7. 최소값이 이미 9라고 알려져 있으므로, 이 배치는 최적입니다.

헷갈리기 쉬운 점

중심만 빽빽하게 칠한다고 잘 퍼지는 것은 아닙니다. 세 이웃이 계속 이어지도록 모양을 만들어야 합니다.

개념 한눈에 보기

개념	나온 문제	기억할 말
왼쪽부터 규칙 따라가기	1	뒤차는 앞차보다 빨라질 수 없다.
양팔저울 차이 생각	2	한쪽에 더하고 다른 쪽에서 빼는 문제다.
가정하고 모순 찾기	3	한 경우를 잡아 보면 거짓말이 드러난다.
조건으로 범위 좁히기	4, 14, 15	가장 작은 값이나 이동 가능 범위가 전체를 묶는다.
경우 나누기	5	한 사람의 선택을 먼저 정하면 작아진다.
짧은 조각 많이 쓰기	6	최소 개수는 긴 조각을 최대한 많이 쓰는 것과 같다.
위치 이동 거리 합	7	이웃 교환 수는 결국 움직인 칸 수다.
최악의 경우 만들기	8	안 좋은 경우를 끝까지 버티게 만들어 본다.
미래를 보고 결정하기	9	가장 늦게 다시 쓸 것을 뽑는다.
그리디 배치	10	값 큰 것을 가능한 늦게 넣는다.
자리별 규칙 보기	11	비트마다 바뀌는 주기가 다르다.
거꾸로 올라가기	12	트리는 뒤집어서 보면 더 쉽다.
점의 둘레 순서 바꾸기	13	교차는 순서가 꼬여서 생긴다.
후보 두 개에서 고르기	16	$+a$와 $-a$ 중 맞는 쪽을 찾는다.
순환 찾기	17	바꾼 열들은 순환을 이루어야 안전하다.
누적합	18	같은 누적합 사이의 합은 0이다.
plus와 max 구분	19	plus는 둘 다, max는 큰 쪽 하나만 중요하다.
번지는 조건 만들기	20	처음 모양이 연쇄 반응을 만들 수 있어야 한다.