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

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

이 문서는 2023 - 중등부 기출문제를 바탕으로, 중학생 기준에서 다시 읽기 쉽게 정리한 학습용 풀이 노트입니다. PDF 제목은 해설이지만 실제로는 문제와 정답 화면이 함께 실린 형식이라, 일부 설명은 학습용으로 다시 구성했습니다.

1. 양팔 저울

문제 한눈에 보기

추 $2$kg, $5$kg, $8$kg을 저울 양쪽에 자유롭게 올려서 15kg 이하 정수 무게를 만들 때, 만들 수 없는 무게를 찾는 문제입니다.

답

$12$kg

핵심 개념

양팔저울은 합보다 차를 만드는 도구입니다.

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

추를 물통 쪽에도, 반대쪽에도 둘 수 있으므로 가능한 무게는 $|\pm 2\pm 5\pm 8|$ 꼴로 생각하는 편이 훨씬 빠릅니다.

단계별 풀이

1. $1=8-5-2$
2. $6=8-2$
3. $11=8+5-2$
4. 이 밖에도 $2,3,5,7,8,10,13,15$ 등을 만들 수 있습니다.
5. 가능한 값을 정리해 보면 $12$는 나오지 않습니다.
6. 따라서 정답은 $12$kg입니다.

헷갈리기 쉬운 점

$8+5-2$처럼 생각해야 합니다. 추를 한쪽에만 올린다고 생각하면 풀이가 막힙니다.

2. 봉투

문제 한눈에 보기

봉투 속 돈이 $9,3,4,5,8$장일 때, 어떤 봉투도 다른 봉투의 2배 이상이 되지 않도록 나누려면 최소 몇 봉투가 필요한지 묻습니다.

답

$7$

핵심 개념

가장 작은 봉투가 정해지면 가장 큰 봉투의 허용 범위도 자동으로 정해집니다.

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

조건이 2배 이상 금지라서, 제일 작은 봉투가 3이면 다른 봉투는 최대 5까지만 가능합니다.

단계별 풀이

1. 이미 $3$이 있는 봉투가 있으므로 최소 봉투 금액은 3보다 클 수 없습니다.
2. 그러면 가능한 봉투 금액은 $3,4,5$뿐입니다.
3. $9$는 $4+5$처럼 두 봉투로 나눠야 합니다.
4. $8$도 $3+5$ 또는 $4+4$처럼 두 봉투로 나눠야 합니다.
5. $3,4,5$는 그대로 둘 수 있습니다.
6. 따라서 총 봉투 수는 $1+1+1+2+2=7$개입니다.

헷갈리기 쉬운 점

이 문제는 돈을 합칠 수는 없고 오직 쪼갤 수만 있습니다.

3. ABAB

문제 한눈에 보기

문자열 bababbaaba를 $a$, $b$, ab, ba로만 나눌 때, 조각 수를 최소로 만드는 문제입니다.

답

$6$

핵심 개념

조각 수를 줄이려면 길이 2인 조각을 최대한 많이 써야 합니다.

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

전체 길이가 10이므로 5조각이 되려면 모든 조각이 길이 2여야 합니다. 이 가능 여부부터 확인하면 됩니다.

단계별 풀이

1. 5조각이 가능하려면 ba | ba | bb | aa | ba처럼 두 글자씩 딱 끊어져야 합니다.
2. 그런데 bb, aa는 허용되지 않습니다.
3. 따라서 5조각은 불가능합니다.
4. 6조각은 예를 들어 ba | ba | b | ba | ab | a처럼 가능합니다.
5. 따라서 최소 조각 수는 $6$입니다.

헷갈리기 쉬운 점

ab, ba만 길이 2 조각으로 허용됩니다. aa, bb는 안 됩니다.

4. 교수와 학생

문제 한눈에 보기

일렬로 놓인 의자 9개에 교수 A, B, C가 먼저 앉습니다. 나중에 학생 6명이 남은 자리에 앉았을 때, 모든 교수가 두 학생 사이에 오도록 교수들이 자리를 고르는 경우의 수를 구하는 문제입니다.

답

$60$

핵심 개념

교수는 끝자리에 앉을 수 없고, 교수끼리 붙어서도 안 됩니다.

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

최종적으로 교수의 양옆이 모두 학생이어야 하므로, 교수 자리의 조건을 좌석 번호 조건으로 바꾸면 바로 셀 수 있습니다.

단계별 풀이

1. 교수 자리는 끝자리 $1,9$에 올 수 없습니다.
2. 또 교수끼리 이웃하면 사이에 학생이 없으므로 안 됩니다.
3. 따라서 교수 3명은 $2$부터 $8$까지의 7자리 중에서 서로 붙지 않게 3자리를 골라야 합니다.
4. 서로 붙지 않게 3자리를 고르는 방법 수는 $10$가지입니다.
5. 그 자리에 A, B, C를 배치하는 순서는 $3!=6$가지입니다.
6. 따라서 전체 경우의 수는 $10\times 6=60$입니다.

헷갈리기 쉬운 점

학생은 나중에 자동으로 남은 자리에 앉습니다. 그러므로 처음에 교수 자리만 잘 고르면 됩니다.

5. 가전제품 교체

문제 한눈에 보기

콘센트 구멍 4개에 대해, 정해진 사용 순서를 따르면서 교체 횟수를 최소로 해야 합니다.

답

$8$

핵심 개념

앞으로 가장 늦게 다시 쓸 물건, 또는 다시 쓰지 않을 물건을 빼는 것이 최적입니다.

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

지금 당장 덜 중요한 것보다 미래에 더 오래 필요 없는 것을 빼야 전체 교체 횟수가 줄어듭니다.

단계별 풀이

1. 처음에는 $(1,2,3,4)$가 꽂혀 있습니다.
2. $5$가 필요하면 앞으로 가장 늦게 다시 나오는 $2$를 뽑습니다.
3. $6$이 필요하면 그다음 기준으로 가장 늦은 $5$를 뽑습니다.
4. $7$이 필요하면 가장 늦게 다시 쓰는 $3$을 뽑습니다.
5. 이런 규칙을 끝까지 반복합니다.
6. 그러면 총 교체 횟수의 최솟값은 $8$이 됩니다.

헷갈리기 쉬운 점

이 문제는 지금이 아니라 앞으로의 순서를 보며 결정해야 합니다.

6. 배수

문제 한눈에 보기

$1$ 이상 $2001$ 이하 자연수 중에서 3의 배수 또는 4의 배수이면서 5의 배수는 아닌 수의 개수를 구합니다.

답

$801$

핵심 개념

포함배제 원리를 두 번 쓰면 됩니다.

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

3의 배수 또는 4의 배수에서 한 번 포함배제를 하고, 그중 5의 배수도 다시 빼야 하기 때문입니다.

단계별 풀이

1. 3의 배수는 $\lfloor 2001/3\rfloor =667$개입니다.
2. 4의 배수는 $\lfloor 2001/4\rfloor =500$개입니다.
3. 둘 다인 12의 배수는 $\lfloor 2001/12\rfloor =166$개입니다.
4. 따라서 3의 배수 또는 4의 배수는 $667+500-166=1001$개입니다.
5. 이제 이 중 5의 배수를 빼야 합니다.
6. 3과 5의 공배수는 15의 배수이므로 $133$개입니다.
7. 4와 5의 공배수는 20의 배수이므로 $100$개입니다.
8. 둘 다 중복된 60의 배수는 $33$개입니다.
9. 따라서 5의 배수이면서 3의 배수 또는 4의 배수는 $133+100-33=200$개입니다.
10. 최종 개수는 $1001-200=801$입니다.

헷갈리기 쉬운 점

또는를 셀 때 중복을 빼고, 5의 배수를 뺄 때도 다시 중복을 조정해야 합니다.

7. 근무 계획

문제 한눈에 보기

작업마다 이득과 마감일이 있고, 기계 2대로 4일 동안 최대 이득을 내는 배치를 찾아야 합니다.

답

$211$

핵심 개념

이득이 큰 작업부터, 가능한 가장 늦은 날에 넣는 그리디가 핵심입니다.

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

이득이 큰 작업을 먼저 살리고, 마감이 빠른 칸은 뒤로 미루지 않는 방식이 전체 합을 가장 크게 만듭니다.

단계별 풀이

1. 기계가 2대이므로 하루에 작업 2개, 전체로는 $8$칸이 있습니다.
2. 이득이 큰 작업부터 보며 마감일 안의 가장 늦은 빈 칸에 넣습니다.
3. 최종적으로 선택되는 작업은 $1,2,3,4,5,7,9,10$번입니다.
4. 이득 합은 $40+35+30+29+25+20+16+16=211$입니다.

헷갈리기 쉬운 점

기계 2대는 하루에 2칸으로 바꿔 생각하면 됩니다.

8. 점 배치

문제 한눈에 보기

한 변 길이 2인 정삼각형에 점 5개를 놓을 때, 어떤 배치를 하더라도 적어도 한 쌍의 거리가 X 이하가 되도록 하는 최소 X를 구합니다.

답

$1.0$

핵심 개념

비둘기집 원리를 쓰려면 삼각형을 작은 삼각형 4개로 나누면 됩니다.

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

점 5개를 4구역에 넣으면 두 점이 같은 구역에 들어간다는 사실을 바로 쓸 수 있기 때문입니다.

단계별 풀이

1. 큰 정삼각형을 한 변 길이 1인 작은 정삼각형 4개로 나눕니다.
2. 점이 5개이므로, 비둘기집 원리에 따라 적어도 두 점은 같은 작은 정삼각형 안에 들어갑니다.
3. 한 변 길이 1인 정삼각형 안의 두 점 사이 거리는 최대 1입니다.
4. 따라서 항상 어떤 한 쌍은 거리 1 이하입니다.
5. 이제 이것이 최소인지 확인해야 합니다.
6. 큰 삼각형의 세 꼭짓점과 두 변의 중점을 잘 고르면 점 5개를 서로 거리가 모두 1 이상 되게 놓을 수 있습니다.
7. 그러므로 1보다 작은 값으로는 보장할 수 없습니다.
8. 따라서 최소 X는 $1.0$입니다.

헷갈리기 쉬운 점

이 문제는 “특정 배치”가 아니라 “어떻게 놓아도 반드시”를 묻는 보장 문제입니다.

9. 이상한 섬

문제 한눈에 보기

신사는 항상 진실, 건달은 항상 거짓말을 합니다. B와 C의 신분을 알아내는 문제입니다.

답

B: 건달, C: 신사

핵심 개념

A는 신사든 건달이든 어차피 나는 신사다라고 말할 수밖에 없습니다.

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

이 문제의 핵심은 A의 대답 내용 자체가 아니라, B가 그 내용을 어떻게 해석해서 전달했는지입니다.

단계별 풀이

1. A가 신사라면 나는 신사다라고 말합니다.
2. A가 건달이어도 나는 건달이다라고는 못 말합니다. 그 말이 참이 되어 버리기 때문입니다.
3. 따라서 A는 어떤 경우에도 나는 신사다라고 말합니다.
4. 그런데 B는 A는 자신이 건달이라고 말했습니다라고 했습니다.
5. 이 말은 거짓이므로 B는 건달입니다.
6. C는 B는 거짓말 중입니다라고 했고, 이것은 참입니다.
7. 따라서 C는 신사입니다.

헷갈리기 쉬운 점

A의 정체는 끝까지 확정되지 않습니다. 문제는 B와 C만 묻고 있습니다.

10. 분수 트리

문제 한눈에 보기

분수 트리에서 루트 $1/1$부터 $29/67$까지 가는 경로를 L, R로 써야 합니다.

답

RLLLLRRRLL

핵심 개념

앞으로 내려가기보다 목표 분수에서 부모를 거꾸로 찾는 방식이 훨씬 간단합니다.

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

앞으로 가면 갈림길이 계속 생기지만, 거꾸로 가면 부모가 하나로 결정됩니다.

단계별 풀이

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

헷갈리기 쉬운 점

거꾸로 찾은 L, R은 마지막에 순서를 뒤집어야 실제 경로가 됩니다.

11. 트리 위의 모임

문제 한눈에 보기

세 정점 $a,b,c$에서 출발한 세 사람이 한 점에 모일 때 드는 최소 이동 거리 합 $f(a,b,c)$를 모든 세 정점쌍에 대해 더하는 문제입니다.

답

$945$

핵심 개념

세 사람이 만나는 최소 이동 거리 합은, 그 세 점을 연결하는 가장 작은 부분트리의 간선 수와 같습니다.

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

어디서 모이든 결국 세 점을 잇는 “필요한 간선들”은 반드시 지나야 합니다. 그래서 정점을 하나하나 세기보다 간선이 몇 번 쓰이는지 세는 편이 쉽습니다.

단계별 풀이

1. 트리의 한 간선을 지우면 정점들이 두 그룹으로 나뉩니다.
2. 어떤 세 점이 이 간선을 반드시 지나려면, 세 점이 양쪽 그룹에 모두 걸쳐 있어야 합니다.
3. 즉 한쪽에 $s$개, 다른 쪽에 $12-s$개가 있을 때 이 간선의 기여도는
4. $C(s,1)C(12-s,2)+C(s,2)C(12-s,1)$입니다.
5. 그림의 각 간선에 대해 한쪽 정점 수를 세어 보면 $1,1,1,1,1,1,2,2,2,3,6$이 나옵니다.
6. 이에 대응하는 기여도는 $55,55,55,55,55,55,100,100,100,135,180$입니다.
7. 모두 더하면 $945$입니다.

헷갈리기 쉬운 점

정점 $v$를 어디로 잡는지 직접 최적화하려 들면 복잡합니다. 이 문제는 간선 기여도 합으로 바꾸는 것이 핵심입니다.

12. 쪽지 시험

문제 한눈에 보기

학생 7명 중 수강생 4명은 자기 시험지를 채점하면 안 되고, 청강생 3명은 자기 시험지를 채점해도 됩니다. 조건을 만족하는 시험지 배분 수를 구합니다.

답

$2790$

핵심 개념

금지되는 것은 수강생 4명의 고정점뿐이므로 포함배제 원리를 쓰면 됩니다.

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

전체 경우는 $7!$로 쉬운데, 금지되는 경우가 “자기 것 채점”처럼 겹쳐 있기 때문입니다.

단계별 풀이

1. 전체 배분 방법은 $7!=5040$가지입니다.
2. 수강생 4명 중 적어도 1명이 자기 시험지를 채점하는 경우를 빼야 합니다.
3. 포함배제를 쓰면
4. $7!-C(4,1)6!+C(4,2)5!-C(4,3)4!+C(4,4)3!$
5. $=5040-4\cdot 720+6\cdot 120-4\cdot 24+6$
6. $=5040-2880+720-96+6$
7. $=2790$

헷갈리기 쉬운 점

청강생은 자기 것을 채점해도 되므로, 포함배제의 대상은 수강생 4명뿐입니다.

13. 얽힌 그래프

문제 한눈에 보기

정점을 움직여서 빨간 교차선이 없게 만들면 되는 평면 그래프 문제입니다.

답

정답은 한 가지가 아닙니다. 안쪽 점들을 바깥 둘레 쪽으로 보내서 6개 점이 둘레 순서대로 놓인 형태를 만들면 됩니다.

핵심 개념

간선이 교차하는 이유는 점들의 상대적 위치가 꼬였기 때문입니다.

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

간선을 바꾸는 것이 아니라 점만 옮길 수 있으므로, 문제는 사실상 “점의 순서를 다시 잡는 문제”입니다.

단계별 풀이

1. 바깥 네 점이 큰 사각형을 이루고 있습니다.
2. 안쪽 두 점이 중앙에 들어와 있어 교차가 생깁니다.
3. 이 두 점을 좌우 바깥쪽으로 조금씩 빼 주면, 전체가 육각형 둘레처럼 정리됩니다.
4. 그러면 서로 교차하던 빨간 간선들을 교차 없이 배치할 수 있습니다.

헷갈리기 쉬운 점

좌표 하나를 맞히는 문제가 아닙니다. 교차만 사라지면 정답입니다.

14. 2층

문제 한눈에 보기

15열짜리 2행 표에서, 같은 열의 위아래만 바꿀 수 있습니다. 원래와는 다른 표이면서 각 행에 중복이 없게 만드는 최소 교환 횟수를 구합니다.

답

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

핵심 개념

각 열을 윗수 → 아랫수라는 화살표로 보면 숫자들의 순환 구조가 보입니다.

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

한 열만 바꾸면 한 숫자를 잃고 다른 숫자를 얻습니다. 따라서 중복 없이 유지하려면 숫자 이동이 순환을 이뤄야 합니다.

단계별 풀이

1. 각 열을 위 숫자에서 아래 숫자로 보내는 대응으로 생각합니다.
2. 그러면 길이 10짜리 순환 하나와 길이 5짜리 순환 하나가 생깁니다.
3. 가장 적게 바꾸려면 짧은 순환만 골라 바꾸면 됩니다.
4. 그 순환은 $1\to 10\to 4\to 11\to 5\to 1$입니다.
5. 이에 해당하는 열이 $4,8,12,13,15$입니다.
6. 이 다섯 열만 바꾸면 두 줄 모두 중복 없는 상태가 됩니다.

헷갈리기 쉬운 점

원래 표도 중복이 없지만, 문제에서 원래 표와 달라야 한다고 했으므로 0번 교환은 허용되지 않습니다.

15. 합이 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$입니다.

헷갈리기 쉬운 점

맨 앞 부분과 맨 뒤 부분은 합이 0이 아니어도 됩니다.

16. 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 정점은 둘 중 큰 값 하나만 남깁니다.

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

큰 수를 무조건 깊은 곳에 두는 것이 아니라, plus를 통과하는 줄에 두어야 실제로 많이 합산됩니다.

단계별 풀이

1. 루트가 plus이므로 왼쪽 큰 덩어리와 오른쪽 큰 덩어리를 둘 다 크게 만들어야 합니다.
2. 오른쪽에는 마지막에 $16$이 더해지고, 중간의 plus도 살아 있으므로 $14,15,16$ 같은 큰 수를 두는 것이 유리합니다.
3. 왼쪽은 max가 많아 한쪽 가지가 버려질 수 있으므로, 큰 수를 plus가 모이는 쪽에 몰아줍니다.
4. 그 결과 그림 예시처럼 배치하면 루트 값이 $81$이 됩니다.

헷갈리기 쉬운 점

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

17. 미로 만들기

문제 한눈에 보기

7×12 격자에서 벽을 적절히 세워 $(1,1)$에서 $(7,12)$까지의 최단 거리를 최대화해야 합니다.

답

최대 목표 점수 배치는 최단 거리 51을 만드는 미로입니다. PDF 21페이지 아래 그림이 한 가지 최적 예시입니다.

핵심 개념

길을 넓게 열어 두면 최단 거리가 짧아집니다. 따라서 한 칸짜리 복도를 길게 굽이치게 만들어야 합니다.

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

최단 거리를 늘리려면 우회길을 많이 만드는 것이 아니라, 유일한 길 자체를 길게 만들어야 합니다.

단계별 풀이

1. 시작점과 도착점을 잇는 흰 칸 복도를 한 줄 통로처럼 만듭니다.
2. 이 통로가 좌우로 지그재그를 반복하게 만들면, 경로가 많은 칸을 지나게 됩니다.
3. PDF 예시를 보면 $39$, $47$, $49$, $51$짜리 미로가 차례로 나옵니다.
4. 이 중 아래쪽 예시가 최단 거리 $51$을 만들므로 만점 배치입니다.
5. 핵심은 각 줄을 거의 끝까지 쓰되, 다음 줄로 넘어가는 문을 한두 곳만 남기는 것입니다.

헷갈리기 쉬운 점

갈 수 있는 칸 수가 많다고 항상 최단 거리가 길어지는 것은 아닙니다. 지름길이 생기면 오히려 짧아집니다.

18. 벌집 채우기

문제 한눈에 보기

처음 몇 칸만 칠한 뒤, 주변 6칸 중 3칸 이상이 칠해지면 번지는 규칙으로 전체를 다 칠하게 만들어야 합니다.

답

최소 시작 칸 수는 $9$

핵심 개념

새 칸이 칠해지려면 이미 칠해진 이웃이 3개 필요하므로, 연쇄 반응이 생기도록 씨앗 모양을 배치해야 합니다.

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

아무 9칸이나 칠하면 퍼지지 않습니다. 3개 이웃 조건이 연속해서 이어지도록 구조를 짜야 합니다.

단계별 풀이

1. PDF 마지막에 최소값이 $m=9$라고 직접 주어집니다.
2. 따라서 9칸으로 실제 성공하는 배치 하나를 찾으면 그것이 최적입니다.
3. 예시처럼 위쪽 대각선 줄과 아래쪽 띄엄띄엄 줄을 조합하면 가운데부터 차례로 번집니다.
4. 이 연쇄가 바깥쪽까지 퍼져 모든 칸이 칠해집니다.

헷갈리기 쉬운 점

가운데에만 몰아 칠하면 바깥쪽이 안 퍼질 수 있습니다. 퍼지는 방향을 미리 생각해야 합니다.

19. 팀원 찾기

문제 한눈에 보기

원탁에 앉은 사람들을 인접 교환만으로 움직여서 같은 팀 번호끼리 서로 이웃하게 만들어야 합니다. 교환 횟수를 최소화해야 합니다.

답

PDF의 다섯 부분문제에 대한 최소 교환 횟수 예시는 각각 $4,8,15,20,28$입니다.

핵심 개념

한 팀의 두 사람을 붙이려면, 그 둘 사이에 끼어 있는 사람 수만큼은 반드시 이동이 필요합니다.

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

인접 교환은 한 번에 한 칸밖에 못 움직입니다. 그래서 “얼마나 멀리 떨어져 있나”가 바로 비용이 됩니다.

단계별 풀이

1. 원탁을 한 줄로 펼쳐 본다고 생각하고, 한 팀의 두 사람을 하나씩 붙여 나갑니다.
2. 어떤 팀의 두 사람이 원을 따라 $k$칸 떨어져 있다면, 더 짧은 쪽 둘레를 따라 당기는 것이 유리합니다.
3. 한 팀을 붙이면 그 팀은 더 이상 건드리지 않고, 남은 팀들에 대해 같은 작업을 반복합니다.
4. 이렇게 하면 이미 붙인 팀을 다시 흩뜨리지 않으면서 최소 교환으로 정리할 수 있습니다.
5. PDF 26~27페이지의 예시 완성 화면에서 최소 횟수가 $4,8,15,20,28$로 제시되어 있습니다.

헷갈리기 쉬운 점

원형이므로 왼쪽과 오른쪽 둘레 중 더 짧은 쪽으로 움직일 수 있습니다.

20. ABBC

문제 한눈에 보기

무향 그래프의 간선 방향을 정해서, 길이 2인 방향 경로 $a\to b\to c$의 개수 ABBC를 최대화해야 합니다.

답

부분문제마다 정답 모양이 다르며, PDF 30~31페이지에 한 가지 최적 방향 예시가 제시되어 있습니다.

핵심 개념

어떤 정점 $b$가 가운데일 때 만들 수 있는 $a\to b\to c$의 개수는 진입 간선 수 × 진출 간선 수입니다.

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

ABBC는 결국 “가운데 정점이 얼마나 많은 2단 경로를 만들어 내느냐”의 합이기 때문입니다.

단계별 풀이

1. 정점 $b$의 차수를 $d$라 하면, $b$에서 만들 수 있는 경로 수는 $\mathrm{indeg}(b)\times \mathrm{outdeg}(b)$입니다.
2. 이 값은 보통 들어오는 간선과 나가는 간선이 한쪽으로만 치우치지 않을 때 커집니다.
3. 따라서 차수가 큰 정점은 가능한 한 중간 허브가 되도록 방향을 잡는 것이 좋습니다.
4. 트리 모양 그래프에서는 가운데 정점을 향하거나, 가운데에서 바깥으로 뻗게 하여 2단 경로를 많이 만듭니다.
5. 조밀한 그래프에서는 순서를 정해 한쪽으로 몰아 방향을 잡되, 중간 정점들의 들어옴/나감이 균형에 가깝게 되도록 조정합니다.
6. PDF 30~31페이지의 화살표 배치는 이런 원리를 적용한 최적 예시입니다.

헷갈리기 쉬운 점

간선 수를 많이 한쪽으로 몰면 어떤 정점은 들어오기만 하거나 나가기만 해서 오히려 2단 경로 수가 줄어듭니다.

개념 한눈에 보기

개념	나온 문제	기억할 말
양팔저울의 차	1	합이 아니라 차를 만든다.
2배 제한	2	가장 작은 봉투가 최대 봉투를 정한다.
조각 최소화	3	길이 2 조각을 최대한 많이 써야 한다.
자리 배치 조합	4	끝자리는 안 되고, 교수끼리 붙으면 안 된다.
미래를 보는 그리디	5	가장 늦게 다시 쓸 것을 뽑는다.
포함배제	6, 12	겹치는 조건은 더하고 빼며 조정한다.
비둘기집 원리	8	5점을 4구역에 넣으면 한 구역에 2점이 간다.
논리 추론	9	A의 말은 사실상 정보가 아니다.
역추적	10	목표에서 부모를 거꾸로 찾는다.
간선 기여도	11	트리 문제는 간선이 몇 번 쓰이는지 센다.
순환 구조	14	교환 가능한 열들은 순환으로 본다.
누적합	15	같은 누적합 사이의 구간합은 0이다.
plus / max 구분	16	plus는 둘 다, max는 큰 쪽 하나만 남긴다.
긴 복도 만들기	17	유일한 길을 지그재그로 길게 만든다.
번지는 조건	18	이웃 3칸 조건이 연쇄로 이어져야 한다.
인접 교환 비용	19	거리만큼 swap이 필요하다.
$indeg\times outdeg$	20	가운데 정점이 많은 2단 경로를 만든다.