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

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

이 문서는 2023 - 고등부 기출문제를 바탕으로, 고등학생 기준에서 다시 읽기 쉽게 정리한 학습용 풀이 노트입니다. 원본 PDF는 정답 중심 자료라서, 서술형 설명은 학습용으로 다시 구성했습니다.

1. 그래프의 지름

문제 한눈에 보기

정점이 10개인 그래프에서 지름이 $1$, $2$, $3$일 때 필요한 간선 수의 최솟값을 각각 구하고, 그 합을 묻는 문제입니다.

답

$63$

핵심 개념

지름이 작으려면 정점들이 서로 가깝게 연결되어 있어야 합니다.

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

지름 $1$, $2$, $3$은 각각 매우 다른 구조를 요구합니다. 경우를 나누면 바로 셀 수 있습니다.

단계별 풀이

1. 지름이 $1$이면 모든 두 정점이 바로 이어져 있어야 하므로 완전그래프입니다.
2. 정점이 10개인 완전그래프의 간선 수는 $10\times 9/2=45$개입니다.
3. 지름이 $2$인 그래프는 중심 하나에서 나머지 9개로 뻗는 별 그래프로 만들 수 있습니다.
4. 이때 간선 수는 $9$개입니다.
5. 지름이 $3$인 그래프는 연결그래프여야 하므로 간선 수가 최소여도 $9$개는 필요합니다.
6. 실제로 가운데 간선 하나를 두고 양쪽에 잎을 붙인 double star 모양 트리는 지름이 $3$이고 간선 수가 $9$개입니다.
7. 따라서 합은 $45+9+9=63$입니다.

헷갈리기 쉬운 점

지름이 $3$이라고 해서 간선을 많이 써야 하는 것은 아닙니다. $\text{연결그래프의 최소 간선 수}=n-1$을 먼저 떠올리면 됩니다.

2. 길 찾기

문제 한눈에 보기

기둥 사이 통로만 따라 입구에서 출구까지 갈 때, 최단 경로가 몇 개인지 묻는 문제입니다.

답

$83160$

핵심 개념

최단 경로는 크게 아래 큰 직사각형, 가운데 연결 통로, 위 큰 정사각형 세 부분으로 나뉩니다.

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

전체를 한 번에 세면 복잡해 보이지만, 최단 경로에서는 가운데 구간이 사실상 강제로 정해져서 앞뒤 두 부분만 세면 됩니다.

단계별 풀이

1. 통로의 폭은 무시하므로, 기둥 사이를 격자 위에서 움직인다고 생각합니다.
2. 입구에서 가운데 세로 통로가 시작되는 점까지 가는 최단 경로를 먼저 셉니다.
3. 이 구간에서는 오른쪽 7번, 위로 4번 움직이면 되고, 순서만 고르면 되므로 경우의 수는
4. $C(11,4)=330$입니다.
5. 그다음 가운데 세로 통로를 따라 위쪽 큰 정사각형의 오른쪽 아래 꼭짓점으로 가는 최단 경로는 하나뿐입니다.
6. 이제 위쪽 $5\times 5$ 격자에서 오른쪽 아래에서 왼쪽 위 출구까지 가야 합니다.
7. 여기서는 왼쪽 5번, 위로 5번 가면 되므로 경우의 수는 $C(10,5)=252$입니다.
8. 따라서 전체 최단 경로 수는 $330\times 252=83160$입니다.

헷갈리기 쉬운 점

가운데 꺾인 통로에서 괜히 돌아가면 더 이상 최단 경로가 아닙니다. 그래서 그 부분은 선택이 없는 구간입니다.

3. 키 순서

문제 한눈에 보기

$A>B$, $B>C$, $E>B$, $D>C$가 알려졌을 때, 키가 작은 순서대로 줄 세우는 방법 수를 구하는 문제입니다.

답

$8$

핵심 개념

알려진 비교만 지키면 되는 부분 순서 문제입니다.

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

누가 반드시 먼저 와야 하는지만 정리하면 경우를 작게 나눌 수 있습니다.

단계별 풀이

1. $A>B>C$이므로 C는 A와 B보다 반드시 앞에 와야 합니다.
2. 또 $D>C$이므로 C는 D보다도 앞에 와야 합니다.
3. 따라서 맨 앞은 반드시 C입니다.
4. 이제 둘째 자리를 생각합니다.
5. B가 둘째이면 남는 A, D, E 사이에는 추가 제약이 없습니다. 이 경우는 $3!=6$가지입니다.
6. D가 둘째이면 그다음에는 B가 와야 합니다. 그래야 $B>C$를 지키면서 A, E가 B 뒤에 올 수 있습니다.
7. 그러면 마지막 둘 A, E의 순서만 정하면 되므로 $2$가지입니다.
8. 전체는 $6+2=8$가지입니다.

헷갈리기 쉬운 점

$E>B$는 E가 반드시 맨 뒤라는 뜻이 아닙니다. B보다만 뒤에 오면 됩니다.

4. 위치 찾기

문제 한눈에 보기

트랙을 도는 5명이 문 앞에서 차례대로 문제를 받습니다. 문제 수는 $1,2,3,\cdots ,14,1,2,\cdots$처럼 반복될 때, 2023번 문제를 풀 사람의 시작 위치를 찾는 문제입니다.

답

$3$번

핵심 개념

사람 순서는 5마다 반복되고, 받는 문제 수는 14마다 반복됩니다.

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

두 반복이 섞여 있으므로, $5$와 $14$를 같이 보는 한 주기를 잡아야 합니다.

단계별 풀이

1. 추월이 불가능하므로 문 앞에 도착하는 순서는 영원히 $1,2,3,4,5,1,2,\cdots$로 반복됩니다.
2. 한편 한 사람이 받는 문제 수는 $1,2,3,\cdots ,14$가 반복됩니다.
3. 두 패턴이 동시에 처음 상태로 돌아오려면 $\mathrm{lcm}(5,14)=70$명이 지나가야 합니다.
4. 이 70명이 푸는 문제 수의 총합은 $5\times (1+2+\cdots +14)=5\times 105=525$입니다.
5. $2023=3\times 525+448$이므로, 2023번 문제는 한 주기 안의 448번째 문제가 누구에게 가는지만 보면 됩니다.
6. 한 주기에서 62번째 사람까지 풀고 나면 누적 문제 수는 $441$입니다.
7. 63번째 사람은 $7$문제를 받아서 $442$번부터 $448$번까지 풉니다.
8. 63번째 사람의 시작 위치는 $1,2,3,4,5$ 반복에서 $3$번입니다.
9. 따라서 2023번 문제를 풀려면 처음에 3번 자리에 있어야 합니다.

헷갈리기 쉬운 점

문제 수는 $14$개 주기로 반복되지만, 사람 번호는 $5$개 주기로 반복됩니다. $105$만 보면 사람 위치가 다시 맞지 않습니다.

5. 식의 성질

문제 한눈에 보기

논리식 $P=(A\mathrm{AND}B)\to C$ 와 $Q=(\mathrm{NOT}C\to \mathrm{NOT}A)\mathrm{OR}(\mathrm{NOT}C\to \mathrm{NOT}B)$가 같은지 묻는 문제입니다.

답

P와 Q는 동일하다

핵심 개념

함의 $X\to Y$는 $\mathrm{NOT}X\mathrm{OR}Y$로 바꿀 수 있습니다.

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

겉모양은 달라도, 모두 OR과 NOT으로 바꾸면 같은 식인지 바로 확인할 수 있습니다.

단계별 풀이

1. $P=(A\mathrm{AND}B)\to C$는
2. $\mathrm{NOT}(A\mathrm{AND}B)\mathrm{OR}C$
3. 즉 $\mathrm{NOT}A\mathrm{OR}\mathrm{NOT}B\mathrm{OR}C$입니다.
4. 이제 Q를 봅니다.
5. $\mathrm{NOT}C\to \mathrm{NOT}A$는 $C\mathrm{OR}\mathrm{NOT}A$입니다.
6. $\mathrm{NOT}C\to \mathrm{NOT}B$는 $C\mathrm{OR}\mathrm{NOT}B$입니다.
7. 따라서 $Q=(C\mathrm{OR}\mathrm{NOT}A)\mathrm{OR}(C\mathrm{OR}\mathrm{NOT}B)=C\mathrm{OR}\mathrm{NOT}A\mathrm{OR}\mathrm{NOT}B$입니다.
8. 결국 P와 Q는 둘 다 $\mathrm{NOT}A\mathrm{OR}\mathrm{NOT}B\mathrm{OR}C$가 되어 완전히 같습니다.

헷갈리기 쉬운 점

$(X\mathrm{OR}Y)\mathrm{OR}(X\mathrm{OR}Z)$는 $X\mathrm{OR}Y\mathrm{OR}Z$로 정리할 수 있습니다. 같은 X를 두 번 쓴다고 다른 식이 되지 않습니다.

6. KOI 문자열

문제 한눈에 보기

길이 12의 문자열 중에서 부분수열 KOI를 만들 수 없는 문자열의 개수를 $2^n\times m$ 꼴로 나타낼 때 $n+m$을 구하는 문제입니다.

답

$58$

핵심 개념

KOI를 아직 얼마나 만든 상태인지에 따라 문자열을 세는 상태 DP가 편합니다.

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

직접 문자열을 다 세는 대신, K를 본 적 있는가, KO까지 만든 적 있는가만 기억하면 다음 글자를 붙일 수 있습니다.

단계별 풀이

1. 상태를 세 가지로 나눕니다.
2. S0: 아직 K조차 만들지 못한 상태
3. S1: K는 만들었지만 KO는 아직 못 만든 상태
4. S2: KO는 만들었지만 KOI는 아직 못 만든 상태
5. 한 글자를 더 붙일 때 상태 전이는 다음과 같습니다.
6. $S0\to S0$는 O, I 두 가지, $S0\to S1$은 K 한 가지입니다.
7. $S1\to S1$은 K, I 두 가지, $S1\to S2$는 O 한 가지입니다.
8. $S2\to S2$는 K, O 두 가지이고, I를 붙이면 KOI가 생겨서 탈락합니다.
9. 이 전이를 12번 적용하면 KOI를 만들지 않는 문자열 수는 $96256$개입니다.
10. $96256=2^{11}\times 47$이므로 $n=11$, $m=47$입니다.
11. 따라서 $n+m=58$입니다.

헷갈리기 쉬운 점

KOI는 연속한 부분문자열이 아니라 부분수열입니다. 중간에 다른 글자가 끼어 있어도 K, O, I 순서만 맞으면 생깁니다.

7. 받아올림

문제 한눈에 보기

$1000$ 이상 $2000$ 이하에서, 연속한 두 수 $x$와 $x+1$을 더할 때 어떤 자리에서도 받아올림이 일어나지 않는 쌍의 개수를 구하는 문제입니다.

답

$156$

핵심 개념

$x+1$이 만들어지는 방식은 끝에 9가 몇 개 붙어 있는가로 나눠서 보면 됩니다.

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

$x+1$은 그냥 각 자리마다 1을 더하는 것이 아니라, 끝의 $9$들이 $0$으로 바뀌며 왼쪽 자리로 넘어갑니다.

단계별 풀이

1. $x$는 네 자리수이고 천의 자리는 항상 $1$입니다.
2. 먼저 끝자리에 $9$가 없는 경우를 봅니다.
3. 일의 자리 $u$에 대해 $u+(u+1)<10$이어야 하므로 $u=0,1,2,3,4$만 가능합니다.
4. 십의 자리와 백의 자리도 받아올림이 없으려면 각 자리 숫자가 $0$부터 $4$여야 합니다.
5. 따라서 이 경우의 수는 $5\times 5\times 5=125$개입니다.
6. 다음은 끝에 $9$가 정확히 한 개 있는 경우입니다. 형태는 1ab9입니다.
7. 이때 십의 자리 $b$는 $b+(b+1)<10$을 만족해야 하므로 $0$부터 $4$까지 가능합니다.
8. 백의 자리 $a$도 $0$부터 $4$까지 가능하므로 $25$개입니다.
9. 끝에 $99$가 붙는 경우는 1a99이고 $a=0,1,2,3,4$라서 $5$개입니다.
10. 끝에 $999$가 붙는 경우는 $1999$ 하나뿐입니다.
11. 합하면 $125+25+5+1=156$입니다.

헷갈리기 쉬운 점

$x+1$을 만들 때 끝의 $9$들은 $0$으로 바뀝니다. 그래서 $1999$도 실제로는 받아올림 없이 $1999+2000$을 만들 수 있습니다.

8. 트리 위의 모임

문제 한눈에 보기

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

답

$945$

핵심 개념

트리에서는 세 사람이 모일 때 각 간선이 몇 번 쓰이는지를 세는 방식이 매우 강력합니다.

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

모든 $a,b,c$를 직접 구하면 너무 많습니다. 대신 한 간선이 전체 합에 얼마나 기여하는지 세면 한 번에 끝납니다.

단계별 풀이

1. 트리에서 세 점의 최소 만남 거리는, 세 점을 잇는 최소 부분트리의 간선 수와 같습니다.
2. 따라서 어떤 간선 하나를 잘라서 정점 수가 $s$와 $12-s$로 나뉜다고 합시다.
3. 이 간선은 세 점이 양쪽에 걸쳐 있을 때만 사용됩니다.
4. 즉, 세 점이 모두 한쪽에 몰려 있지 않은 경우의 수만 세면 됩니다.
5. 그 수는 $C(12,3)-C(s,3)-C(12-s,3)$입니다.
6. 그림의 트리에서 각 간선에 대해 작은 쪽 정점 수를 읽으면 $1,1,1,1,1,1,2,2,2,3,6$입니다.
7. 따라서 간선별 기여는 차례로 $55,55,55,55,55,55,100,100,100,135,180$입니다.
8. 모두 더하면 $6\times 55+3\times 100+135+180=945$입니다.

헷갈리기 쉬운 점

이 문제는 어디에서 만나는가를 직접 고를 필요가 없습니다. 트리에서는 간선 기여도로 바꾸면 자동으로 해결됩니다.

9. 리그전

문제 한눈에 보기

네 팀의 리그 결과가 몇 가지 조건을 만족할 때, A와 C의 경기 결과가 무엇인지 묻는 문제입니다.

답

A가 이기거나 비겼다

핵심 개념

문장 중 하나가 이미 아주 강한 조건을 줍니다.

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

불필요한 조건까지 다 쓸 필요 없이, 가장 강한 조건 하나만 보아도 선택지를 바로 줄일 수 있습니다.

단계별 풀이

1. 문제에서 A와 D는 모두 패가 없다고 했습니다.
2. 따라서 A는 누구에게도 지지 않았습니다.
3. 특히 A와 C의 경기에서도 A가 질 수는 없습니다.
4. 그러므로 가능한 결과는 A 승 또는 무승부뿐입니다.
5. 보기 중 이 둘을 모두 포함하는 선택지는 A가 이기거나 비겼다입니다.

헷갈리기 쉬운 점

다른 조건들도 모두 참이지만, 이 질문 자체를 푸는 데는 A가 패가 없다는 사실만으로 충분합니다.

10. 쪽지 시험

문제 한눈에 보기

7명이 시험지를 하나씩 채점할 때, 수강생 4명만 자기 시험지를 채점하면 안 됩니다. 이 조건을 만족하는 배정 수를 구하는 문제입니다.

답

$2790$

핵심 개념

특정 몇 명만 자기 것을 하면 안 된다는 포함배제가 가장 자연스럽습니다.

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

전체 $7!$개에서 금지된 경우를 빼되, 두 사람 이상이 동시에 자기 것을 맡는 경우가 겹쳐서 여러 번 빠지므로 다시 더해 줘야 합니다.

단계별 풀이

1. 전체 배정 방법 수는 $7!=5040$입니다.
2. 수강생 4명 중 한 명이 자기 시험지를 맡는 경우를 빼겠습니다.
3. 한 명을 고르는 방법은 $C(4,1)$이고, 나머지 6장은 아무렇게나 배정하므로 $C(4,1)\times 6!=4\times 720$을 뺍니다.
4. 그런데 두 명이 동시에 자기 것을 맡는 경우는 두 번 빠졌으므로 다시 더합니다.
5. 그 수는 $C(4,2)\times 5!=6\times 120$입니다.
6. 세 명이 동시에 자기 것을 맡는 경우는 다시 빼고, 네 명 모두 자기 것을 맡는 경우는 다시 더합니다.
7. 따라서 답은
8. $7!-C(4,1)6!+C(4,2)5!-C(4,3)4!+C(4,4)3!$
9. $=5040-2880+720-96+6=2790$입니다.

헷갈리기 쉬운 점

청강생 3명은 자기 시험지를 채점해도 됩니다. 따라서 포함배제의 대상은 수강생 4명뿐입니다.

11. 보물 상자

문제 한눈에 보기

보물이 들어 있을 확률과 꺼내는 비용이 다른 5개 상자를 어떤 순서로 열어야 총 기대 비용이 최소가 되는지 묻는 문제입니다.

답

$2475$

핵심 개념

두 상자의 순서를 비교하면 비용 / 확률이 작은 상자를 먼저 여는 것이 유리합니다.

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

모든 순서를 다 시험할 수도 있지만, 어떤 상자를 앞에 둘지 판단하는 간단한 기준이 있으면 훨씬 빨라집니다.

단계별 풀이

1. 두 상자 X, Y만 있다고 합시다.
2. X를 먼저 열면 기대 비용은 $cX+(1-pX)cY$입니다.
3. Y를 먼저 열면 기대 비용은 $cY+(1-pY)cX$입니다.
4. 앞의 식이 더 작도록 정리하면 $cX/pX<=cY/pY$가 됩니다.
5. 따라서 비용 / 확률이 작은 순서대로 열면 됩니다.
6. 각 상자에 대해 계산하면
7. $A:500/0.10=5000$
8. $B:600/0.15=4000$
9. $C:900/0.25=3600$
10. $D:700/0.15\approx 4666.7$
11. $E:1500/0.35\approx 4285.7$
12. 따라서 최적 순서는 $C\to B\to E\to D\to A$입니다.
13. 이 순서의 기대 비용은
14. $900+0.75\times 600+0.60\times 1500+0.25\times 700+0.10\times 500$
15. $=900+450+900+175+50=2475$입니다.

헷갈리기 쉬운 점

확률이 가장 큰 상자를 무조건 먼저 열면 안 됩니다. 확률과 비용을 같이 봐야 합니다.

12. 약수 게임

문제 한눈에 보기

조약돌이 $n$개 있을 때 자기 차례에 $n$의 약수 $d$개를 가져가서 $n-d$개로 만드는 게임입니다. $1$ 이상 $1000$ 이하에서 선공이 이기는 $n$의 개수를 구하는 문제입니다.

답

$495$

핵심 개념

이 게임은 홀수, 2의 거듭제곱을 기준으로 승패가 깔끔하게 갈립니다.

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

작은 수를 몇 개 써 보면 패배 위치가 $1,2,3,5,7,8,9,11,\cdots$처럼 규칙적으로 나타납니다. 이 규칙을 증명하면 개수까지 바로 셀 수 있습니다.

단계별 풀이

1. 결론부터 말하면, 패배 위치는
2. 모든 홀수와 2의 홀수 제곱 꼴의 짝수, 즉 $2,8,32,128,512$입니다.
3. 먼저 $n$이 홀수라고 합시다.
4. 약수 $d$도 홀수이므로 $n-d=d(q-1)$ 꼴의 짝수가 됩니다.
5. 여기서 $d>=3$ 또는 아예 움직일 수 없는 소수이므로, 도착 위치는 항상 홀수가 아닌 이기는 짝수가 됩니다. 따라서 홀수는 패배 위치입니다.
6. 다음으로 $n=2^{2k+1}$ 꼴이라고 합시다.
7. 가능한 약수는 모두 $2^j$이고, $n-2^j=2^j(2^{2k+1-j}-1)$입니다.
8. 이 값은 항상 홀수 인수를 가지거나 2의 짝수 제곱이 되어 모두 이기는 위치가 됩니다.
9. 따라서 $2^{2k+1}$도 패배 위치입니다.
10. 반대로 $n$이 짝수이면서 홀수 인수 m > 1을 가지면, 약수로 $d=m$을 고를 수 있습니다.
11. 그러면 $n-d=m(2^t-1)$은 홀수가 되어 패배 위치로 보낼 수 있습니다.
12. 또 $n=2^{2k}$ 꼴이면 $d=2^{2k-1}$을 골라 $2^{2k-1}$로 보낼 수 있는데, 이것은 2의 홀수 제곱 꼴 패배 위치입니다.
13. 결국 이기는 수는 짝수 중에서 $2,8,32,128,512$만 뺀 나머지입니다.
14. $1$부터 $1000$까지 짝수는 $500$개이므로, 선공이 이기는 수는 $500-5=495$개입니다.

헷갈리기 쉬운 점

홀수는 전부 진다고 해서 짝수는 전부 이긴다가 아닙니다. $2,8,32,128,512$는 예외입니다.

13. 원판 배치하기

문제 한눈에 보기

점 7개 위에 원판 7개를 놓되, 이웃한 두 원판이 서로 외접하도록 배치하는 구성 문제입니다.

답

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

핵심 개념

외접 조건은 반지름의 합 = 중심 사이 거리입니다.

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

원판의 색보다 중요한 것은 반지름의 크기입니다. 어떤 원판끼리 이웃해야 하는지가 거리로 정해집니다.

단계별 풀이

1. 점 사이 거리는 이미 정해져 있습니다.
2. 이웃한 두 원판은 그 거리와 정확히 맞는 반지름 합을 가져야 합니다.
3. 따라서 큰 간격 옆에는 큰 원판이, 작은 간격 옆에는 작은 원판이 와야 합니다.
4. 그림 아래쪽 예시는 이런 반지름 합 조건을 모두 만족하는 한 가지 배치입니다.
5. 이 문제는 정답이 하나만 있는 것이 아니라, 조건만 만족하면 됩니다.

헷갈리기 쉬운 점

원판이 겹치지 않는 것만으로는 부족합니다. 이웃한 두 원판이 정확히 외접해야 합니다.

14. 2층

문제 한눈에 보기

2행 15열 표에서 같은 열의 위아래만 바꾸어, 원래와는 다르면서 각 행에 중복이 없게 만드는 최소 교환 횟수를 구하는 문제입니다.

답

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

핵심 개념

각 열을 윗수 -> 아랫수라는 화살표로 보면 순환 구조가 드러납니다.

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

열을 바꾼다는 것은 한 숫자를 다른 행으로 보내는 일입니다. 중복 없이 유지하려면 이 이동이 순환이어야 합니다.

단계별 풀이

1. 각 열을 위 숫자에서 아래 숫자로 보내는 대응으로 생각합니다.
2. 그러면 숫자들의 이동은 길이 10짜리 순환 하나와 길이 5짜리 순환 하나로 나뉩니다.
3. 원래 표와 달라야 하므로 최소 한 개 이상의 순환은 골라서 뒤집어야 합니다.
4. 가장 적게 바꾸려면 더 짧은 길이 5 순환만 고르면 됩니다.
5. 그 순환은 $1\to 10\to 4\to 11\to 5\to 1$입니다.
6. 이에 해당하는 열이 $4,8,12,13,15$입니다.
7. 따라서 최소 교환 횟수는 $5$입니다.

헷갈리기 쉬운 점

원래 표가 이미 중복이 없더라도 원래와 달라야 한다는 조건 때문에 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. max 아래에서는 둘 중 큰 값 하나만 남으므로, 거기에 큰 수를 두 개 다 몰아도 하나는 버려집니다.
3. 반대로 plus 아래에서는 큰 수들이 그대로 합쳐집니다.
4. 그래서 큰 수 $14,15,16$은 오른쪽 아래 plus 줄기에 두는 것이 유리합니다.
5. 왼쪽도 마찬가지로 plus가 겹치는 줄기에 큰 수를 배치하면 루트 값이 커집니다.
6. 그림과 같은 배치를 하면 루트 값이 $81$이 됩니다.

헷갈리기 쉬운 점

max는 큰 수 하나만 살린다는 점을 놓치면, 큰 수를 낭비하는 배치를 하게 됩니다.

17. 벌집 채우기

문제 한눈에 보기

처음 몇 칸만 색칠한 뒤, 이웃 6칸 중 3칸 이상이 칠해지면 번지는 규칙으로 전체를 다 칠하게 만드는 최소 시작 칸 수를 묻는 문제입니다.

답

최소 시작 칸 수는 $9$

핵심 개념

이 문제는 번지는 규칙이 연쇄적으로 계속 이어지도록 씨앗 칸을 놓아야 합니다.

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

아무 9칸이나 칠하면 멈춰 버립니다. 다음 칸이 계속 이웃 3개를 만족하도록 구조를 만들어야 합니다.

단계별 풀이

1. 원본 PDF에 최소값이 $m=9$라고 제시되어 있습니다.
2. 따라서 할 일은 9칸으로 실제로 전체가 채워지는 배치 하나를 찾는 것입니다.
3. 그림의 예시처럼 가운데와 대각선 방향으로 씨앗을 배치하면, 먼저 중앙 근처 칸들이 채워집니다.
4. 그다음 새로 채워진 칸들이 다시 바깥 칸들의 이웃 수를 3 이상으로 만들어 줍니다.
5. 이런 연쇄가 끝까지 이어져 전체가 모두 칠해집니다.
6. 따라서 최소 시작 칸 수는 $9$입니다.

헷갈리기 쉬운 점

가운데에만 몰아 칠하면 바깥쪽으로 번지지 않을 수 있습니다. 다음 단계를 계속 생각해야 합니다.

18. 팀원 찾기

문제 한눈에 보기

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

답

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

핵심 개념

인접 교환은 사람을 한 번에 한 칸만 움직입니다. 그래서 얼마나 떨어져 있는가가 바로 비용이 됩니다.

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

어떤 팀을 붙일 때는 원을 따라 두 사람 사이의 더 짧은 쪽으로 당겨야 총 교환 수가 줄어듭니다.

단계별 풀이

1. 한 팀의 두 사람이 원탁에서 떨어진 거리를 봅니다.
2. 왼쪽으로 모으는 방법과 오른쪽으로 모으는 방법 중 더 짧은 쪽을 고릅니다.
3. 인접 교환 한 번은 거리를 정확히 $1$만 줄입니다.
4. 따라서 한 팀을 붙이는 데 필요한 최소 교환 수는 두 사람 사이에 끼어 있는 사람 수와 같습니다.
5. 한 팀을 붙이고 나면 그 팀은 하나의 덩어리처럼 보고, 남은 팀들에 대해 같은 작업을 반복합니다.
6. PDF 예시 완성 화면의 최소 횟수는 차례로 $4,8,15,20,28$입니다.

헷갈리기 쉬운 점

원형이라서 한 방향만 보는 것이 아닙니다. 항상 두 방향 중 더 짧은 쪽을 봐야 합니다.

19. ABBC

문제 한눈에 보기

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

답

부분문제마다 정답 방향이 다르며, PDF 27~28페이지에 한 가지 최적 배치 예시가 제시되어 있습니다.

핵심 개념

정점 $b$가 가운데일 때 만들 수 있는 경로 수는 $\mathrm{indeg}(b)\times \mathrm{outdeg}(b)$입니다.

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

ABBC 전체는 결국 모든 정점이 가운데가 되었을 때 만드는 2단 경로 수의 합입니다.

단계별 풀이

1. 어떤 정점 $b$에 들어오는 간선 수를 $\mathrm{indeg}(b)$, 나가는 간선 수를 $\mathrm{outdeg}(b)$라고 합시다.
2. $a\to b\to c$를 만들려면 들어오는 간선 하나와 나가는 간선 하나를 고르면 되므로, 정점 $b$의 기여는 $\mathrm{indeg}(b)\times \mathrm{outdeg}(b)$입니다.
3. 따라서 차수가 큰 정점은 들어오는 수와 나가는 수가 한쪽으로만 치우치지 않게 만드는 것이 좋습니다.
4. 예를 들어 차수가 $d$인 정점에서는 $d/2$와 $d/2$에 가깝게 나누는 것이 곱을 크게 만듭니다.
5. 그래서 최적 방향 배치는 보통 중간 허브가 되는 정점들에 대해 화살표를 균형 있게 배정하는 모양이 됩니다.
6. PDF 27~28페이지의 화살표들은 이 원리를 적용한 한 가지 최적 예시입니다.

헷갈리기 쉬운 점

한 정점에서 화살표를 전부 한쪽으로 몰면 $indeg\times outdeg$가 $0$이 되어 오히려 손해입니다.

20. 교집합과 격자판

문제 한눈에 보기

행과 열에 $1,2,3,4$의 서로 다른 부분집합 16개를 하나씩 배정했을 때, 교집합이 공집합이 아니면 칠해지는 격자판입니다. 오른쪽 격자판의 행과 열을 바꾸어 왼쪽과 같게 만들어야 합니다.

답

정답은 하나가 아닙니다. 원소 개수와 교집합 패턴을 이용해 행과 열의 집합 이름을 복원한 뒤, 그 순서대로 맞추면 됩니다.

핵심 개념

한 행이 몇 칸 칠해지는지는 그 행에 배정된 부분집합의 원소 개수만으로 결정됩니다.

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

16개의 부분집합 이름을 처음부터 다 맞히려 하면 너무 복잡합니다. 먼저 크기 0, 1, 2, 3, 4를 구분하면 문제가 훨씬 작아집니다.

단계별 풀이

1. 한 행에 집합 S가 배정되어 있다고 합시다.
2. 열 집합과 교집합이 비어 있는 경우는 S의 여집합의 부분집합을 고를 때뿐입니다.
3. 따라서 그 행에서 칠해지는 칸 수는 $16-2^{4-|S|}$입니다.
4. 그래서 행의 검은 칸 수만 세면 집합 크기를 구분할 수 있습니다.
5. $0$개면 공집합, $8$개면 한 원소 집합, $12$개면 두 원소 집합, $14$개면 세 원소 집합, $15$개면 전체집합입니다.
6. 이제 8개 칠해진 행 4개를 찾으면 이것들이 $1,2,3,4$에 해당합니다.
7. 어떤 12개 칠해진 행은 이 네 행 중 정확히 두 행과만 겹치므로, 그 두 원소가 들어 있는 2원소 집합임을 알 수 있습니다.
8. 14개 칠해진 행은 4개의 singleton 중 정확히 하나와만 겹치지 않으므로, 빠진 원소가 무엇인지 알 수 있습니다.
9. 열도 같은 방법으로 이름을 붙일 수 있습니다.
10. 마지막으로 왼쪽 판의 순서에 맞게 오른쪽 판의 행과 열을 바꾸면 완성입니다.

헷갈리기 쉬운 점

이 문제는 최소 교환 횟수를 묻지 않습니다. 조건만 맞으면 어떤 순서로 바꿔도 됩니다.

개념 한눈에 보기

개념	나온 문제	기억할 말
지름과 최소 간선	1	지름이 1이면 완전그래프, 연결 최소는 $n-1$이다.
격자 최단 경로	2	강제 구간을 먼저 떼어 내면 조합으로 센다.
부분 순서	3	반드시 먼저 와야 하는 사람부터 고른다.
주기와 최소공배수	4	사람 주기와 문제 수 주기를 함께 본다.
논리식 정리	5	$X\to Y$는 $\mathrm{NOT}X\mathrm{OR}Y$로 바꾼다.
상태 DP	6	K, KO, KOI 직전 상태만 기억하면 된다.
자리올림 분석	7	끝의 $9$ 개수로 경우를 나눈다.
트리 간선 기여도	8	한 간선이 양쪽으로 나뉘는 삼중항만 센다.
조건 읽기	9	가장 강한 조건 하나가 답을 정할 때가 있다.
포함배제	10	금지된 고정점을 빼고, 겹친 만큼 다시 더한다.
기대값 그리디	11	비용 / 확률이 작은 상자를 먼저 연다.
게임 분류	12	홀수와 특정 2의 거듭제곱이 패배 위치다.
외접 조건	13	반지름 합이 거리와 같아야 한다.
순환 구조	14	열 바꾸기는 숫자 이동 순환으로 본다.
누적합	15	같은 누적합 사이 구간합은 0이다.
max와 plus	16	큰 수는 plus를 많이 통과하는 곳에 둔다.
번짐 시뮬레이션	17	다음 단계까지 살아나는 씨앗을 배치한다.
인접 교환 비용	18	한 번에 한 칸만 움직일 수 있다.
$indeg\times outdeg$	19	가운데 정점의 기여를 최대로 만든다.
집합 서명	20	행과 열의 검은 칸 수가 집합 크기를 알려 준다.