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

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

이 문서는 2025 - 고등부 기출문제를 바탕으로, 고등학생 기준에서 다시 읽기 쉽게 정리한 학습용 풀이 노트입니다. 2025 고등부 자료는 공식 해설을 포함하고 있으므로, 아이디어는 해설을 따르되 계산 흐름이 한 번에 보이도록 다시 구성했습니다.

1. 스택

문제 한눈에 보기

주어진 push, pop 연산을 그대로 따라가서 거짓인 보기를 찾는 문제입니다.

답

거짓인 문장은 스택에서 마지막에서 세 번째로 빠져나온 자연수는 6이다.입니다.

핵심 개념

스택은 LIFO입니다.

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

pop 순서만 정확히 적으면 보기 판단은 바로 끝납니다.

단계별 풀이

1. pop 순서를 실제로 적으면 $4,3,9,8,7,11,10,6,5,2,1$입니다.
2. 따라서 마지막에서 세 번째 원소는 $6$이 아니라 $5$입니다.

헷갈리기 쉬운 점

“마지막에서 세 번째”는 뒤에서 세야 합니다.

2. 달리기 시합

문제 한눈에 보기

연속된 도착 순간 정보로 속력 비를 복원해, A가 도착할 때 D가 몇 미터 남는지 구하는 문제입니다.

답

$36$

핵심 개념

같은 시간 동안 이동한 거리의 비는 속력의 비와 같습니다.

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

문장에 나온 “50m 중 몇 m 남았는가”는 곧 속력 비를 주는 정보이기 때문입니다.

단계별 풀이

1. A가 도착할 때 B는 40m를 달렸으므로 $v_B=4/5v_A$입니다.
2. B가 도착할 때 C는 35m를 달렸으므로 $v_C=7/10v_B$입니다.
3. C가 도착할 때 D는 25m를 달렸으므로 $v_D=1/2v_C$입니다.
4. 따라서

$v_D=v_A\times 4/5\times 7/10\times 1/2=7/25v_A$

5. A가 도착할 때 D는 $50\times 7/25=14\mathrm{m}$를 달립니다.
6. 남은 거리는 $50-14=36\mathrm{m}$입니다.

헷갈리기 쉬운 점

남은 거리에서 바로 비를 잡지 말고 먼저 달린 거리로 바꾸어야 합니다.

3. 마법 문자열

문제 한눈에 보기

최종 문자열이 주어졌을 때, 원래 외친 주문열을 복원하는 문제입니다.

답

$12122211221$

핵심 개념

정방향 시뮬레이션보다 역연산이 쉽습니다.

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

$2$ 주문이 전체 뒤집기를 포함하므로, 마지막 문자열에서 되감는 편이 훨씬 단순합니다.

단계별 풀이

1. 마지막 글자가 $1$이면 마지막 주문은 $1$이므로 끝의 $1$만 지웁니다.
2. 마지막 글자가 $2$이면 마지막 주문은 $2$이므로 끝의 $2$를 지우고 남은 문자열을 뒤집습니다.
3. $221211221121$에 이 연산을 반복하면 $1$까지 되돌아갑니다.
4. 역순으로 얻은 주문을 다시 뒤집으면 정답은 $12122211221$입니다.

헷갈리기 쉬운 점

역방향으로 찾은 주문열은 마지막에 순서를 뒤집어야 합니다.

4. 숫자 제거

문제 한눈에 보기

주어진 9자리 수에서 5자리를 지워 얻는 4자리 수들을 내림차순으로 정렬했을 때, 49번째를 구하는 문제입니다.

답

$5673$

핵심 개념

사전식 내림차순으로 rank를 세면 됩니다.

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

4자리 수의 대소는 앞자리부터 결정되므로, 첫 자리부터 묶어 세는 것이 가장 빠릅니다.

단계별 풀이

1. 첫 자리가 $9$인 경우는 $C(7,3)=35$개입니다.
2. 첫 자리가 $8$인 경우는 $8734$ 하나뿐입니다.
3. 첫 자리가 $6$인 경우는 $4$개입니다.
4. 따라서 49번째는 $5$로 시작하는 수들 중 9번째입니다.
5. $5$ 뒤의 3자리 부분수열을 내림차순으로 적으면
6. $874,873,834,734,687,684,683,674,673,634$입니다.
7. 그중 9번째가 $673$이므로 답은 $5673$입니다.

헷갈리기 쉬운 점

부분수열이므로 원래 자리 순서는 반드시 유지되어야 합니다.

5. 19 단의 자릿수

문제 한눈에 보기

19단표 전체의 자릿수 합을 구하는 문제입니다.

답

$845$

핵심 개념

한 자리 수, 두 자리 수, 세 자리 수 개수를 나눈 뒤 가중합을 계산합니다.

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

문제의 식 $A+2B+3C$가 바로 전체 자릿수 합입니다.

단계별 풀이

1. 전체 칸은 $19^2=361$개입니다.
2. 한 자리 수는 곱이 $9$ 이하인 칸이고, 세어 보면 $23$개입니다.
3. 세 자리 수는 곱이 $100$ 이상인 칸이고, 세어 보면 $146$개입니다.
4. 따라서 두 자리 수는 $361-23-146=192$개입니다.
5. 전체 자릿수 합은

$23+2\times 192+3\times 146=845$

입니다.

헷갈리기 쉬운 점

칸 수와 자릿수는 다르므로, 두 자리 수와 세 자리 수는 각각 2배, 3배를 해 주어야 합니다.

6. 투표 결과

문제 한눈에 보기

7명이 3명의 후보에게 투표할 때, A 득표수가 B 득표수보다 큰 경우의 수를 구하는 문제입니다.

답

$897$

핵심 개념

대칭성과 다항계수를 함께 씁니다.

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

$A>B$와 $A<B$는 완전히 대칭이므로, $A=B$만 세면 나머지를 둘로 나눌 수 있습니다.

단계별 풀이

1. 전체 경우의 수는 $3^7=2187$입니다.
2. $A>B$와 $A<B$는 같은 수입니다.
3. 따라서 $A=B$인 경우 수를 세어 빼면 됩니다.
4. $A=B=k$이면 C는 $7-2k$표를 받으므로 $k=0,1,2,3$만 가능합니다.
5. 각 경우 수는

$1,42,210,140$

입니다. 6. 합은 $393$입니다. 7. 그러므로

$A>B=(2187-393)/2=897$

입니다.

헷갈리기 쉬운 점

$A=B$인 경우는 어느 쪽 절반에도 들어가지 않으므로 먼저 분리해야 합니다.

7. 돌 가져가기 게임

문제 한눈에 보기

A는 13의 배수 개, B는 9의 배수 개만 가져갈 수 있을 때, A가 이기는 시작 돌 개수의 개수를 묻는 게임 문제입니다.

답

$684$

핵심 개념

나머지류와 귀납적 winning/losing 분류를 사용합니다.

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

A의 수는 13의 배수, B의 수는 9의 배수이므로, 작은 잔여 구간으로 몰아넣는 전략이 잘 보입니다.

단계별 풀이

1. 돌이 $0$개부터 $8$개까지면 B는 아무 것도 가져갈 수 없으므로, A가 직전에 이런 상태를 만들면 이깁니다.
2. $n=13q+r$로 두겠습니다.
3. $0\le r\le 8$이면 A는 13q개를 가져가서 정확히 $r$개를 남길 수 있습니다.
4. 그러면 B는 9의 배수를 가져갈 수 없으므로 집니다.
5. 반대로 $9\le r\le 12$라고 합시다.
6. A가 무엇을 가져가도 남는 수는 여전히 $13t+r$ 꼴입니다.
7. 그런데 길이 9인 구간 $[N-8,N]$ 안에는 반드시 9의 배수가 하나 있으므로, B는 적당한 9의 배수 개를 가져가서 $0$부터 $8$개를 남길 수 있습니다.
8. 그러면 다음 차례 A가 집니다.
9. 따라서 A의 winning position은 정확히 $13$으로 나눈 나머지가 $0,1,2,3,4,5,6,7,8$인 수들입니다. 단, 실제로 첫 수를 가져가려면 $n\ge 13$이어야 합니다.
10. $1$부터 $1000$까지는 $13$개씩 묶인 완전한 블록이 $76$개 있고, 각 블록마다 A의 winning position이 $9$개입니다.
11. 나머지 $12$개에서는 winning residue가 없습니다.
12. 따라서 총 개수는 $76\times 9=684$입니다.

헷갈리기 쉬운 점

$1$부터 $8$은 나머지가 작아 보여도 A가 첫 수를 가져갈 수 없으므로 winning position이 아닙니다.

8. 거리 점프

문제 한눈에 보기

함수 $f$를 10번 반복해서 0이 되는 모든 정수 $x$를 찾고, 개수와 합을 더하는 문제입니다.

답

$1410$

핵심 개념

역상 집합을 단계적으로 구합니다.

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

$f^{10}(x)=0$을 직접 풀기보다, 0으로 오는 값들의 집합을 거꾸로 확장하는 편이 구조를 드러냅니다.

단계별 풀이

1. 한 번에 0으로 가는 값은 $[20,25]$의 6개 정수입니다.
2. 이 집합의 역상을 구하면 다시 길이 6짜리 두 구간으로 나뉩니다.
3. 이를 반복하면 10단계 뒤 집합은 다음 10개 구간의 합집합이 됩니다.

$[-205,-200],[-155,-150],[-105,-100],[-55,-50],[-5,0],[45,50],[95,100],[145,150],[195,200],[245,250]$

4. 각 구간은 양 끝을 포함하고 길이 6이므로 전체 개수는 $60$입니다.
5. 이들의 합은 $1350$입니다.
6. 따라서 $c+s=60+1350=1410$입니다.

헷갈리기 쉬운 점

정수 전체가 대상이므로 음수도 빠지지 않습니다.

9. 홀수 평균

문제 한눈에 보기

$1\le x<y<z\le 30$인 세 정수의 평균이 홀수가 되는 경우의 수를 구하는 문제입니다.

답

$680$

핵심 개념

평균이 홀수라는 말은 $x+y+z\equiv 3(\mathrm{mod}6)$와 같습니다.

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

홀수이면서 3으로 나누어떨어져야 하므로, mod 6으로 보는 순간 경우를 체계적으로 셀 수 있습니다.

단계별 풀이

1. 평균이 홀수 정수라면

$x+y+z=3\times (\text{홀수})$

이므로 합은 $6$으로 나눈 나머지가 $3$입니다. 2. $1$부터 $30$까지는 각 나머지류 $0,1,2,3,4,5\mathrm{mod}6$에 정확히 $5$개씩 있습니다. 3. 세 나머지의 합이 $3\mathrm{mod}6$이 되는 경우를 세면 다음 10가지입니다.

$(0,0,3),(0,1,2),(0,4,5),(1,1,1),(1,3,5),(1,4,4),(2,2,5),(2,3,4),(3,3,3),(5,5,5)$

4. 서로 다른 세 나머지인 경우는 4종류이고, 각각 $5^3=125$가지이므로 $500$가지입니다.
5. 두 개가 같은 경우는 3종류이고, 각각 $C(5,2)\times 5=50$가지이므로 $150$가지입니다.
6. 세 개가 같은 경우는 3종류이고, 각각 $C(5,3)=10$가지이므로 $30$가지입니다.
7. 전체는 $500+150+30=680$입니다.

헷갈리기 쉬운 점

평균이 홀수라는 조건은 합이 홀수라는 말보다 강합니다. 동시에 3으로도 나누어져야 합니다.

10. 개구리 점프

문제 한눈에 보기

주어진 초기 배치에서 점프를 반복해 만들 수 있는 서로 다른 개구리 배치 수를 구하는 문제입니다.

답

$5005$

핵심 개념

점프는 개구리들의 상대적 순서를 바꾸지 못합니다. 결국 상태는 빈칸 배치로 환원됩니다.

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

상태를 직접 모두 손으로 세는 것은 어렵지만, 순서 보존을 이용하면 조합 문제로 떨어집니다.

단계별 풀이

1. 각 점프는 두 칸 이동이므로, 개구리들의 왼쪽부터의 순서는 유지됩니다.
2. 따라서 배치를 구별하는 핵심은 “빈칸들이 개구리들 사이 어디에 놓였는가”입니다.
3. 해설의 조합 정리를 따르면 가능한 상태 수는

$C(15,6)$

으로 계산됩니다. 4. 따라서 답은

$C(15,6)=5005$

입니다.

헷갈리기 쉬운 점

개구리들이 서로 구별되지 않아도, 순서가 보존된다는 사실은 여전히 중요한 제약입니다.

11. 팀 나누기

문제 한눈에 보기

A팀은 항상 가장 작은 남은 번호를 뽑고, B팀은 선호순위에 따라 뽑을 때 가능한 서로 다른 최종 팀 구성을 세는 문제입니다.

답

$211$

핵심 개념

최종 A팀 멤버를 오름차순 $a_1<\cdots <a_6$로 두면, 각 $a_i$에 강한 상한이 생깁니다.

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

A는 자기 차례마다 “남은 선수 중 최소 번호”를 강제로 고르므로, 어느 시점까지 최소 몇 명이 사라져 있어야 하는지가 바로 조건이 됩니다.

단계별 풀이

1. A의 선택은 1번째, 4번째, 5번째, 8번째, 9번째, 12번째에 일어납니다.
2. 따라서 A의 두 번째 픽 직전에는 이미 3명이 뽑혀 있고, 세 번째 픽 직전에는 4명이, 네 번째 픽 직전에는 7명이 빠져 있습니다.
3. 그래서 최종 A팀 멤버를 $a_1<\cdots <a_6$라 하면

$a_1\le 1,a_2\le 4,a_3\le 5,a_4\le 8,a_5\le 9,a_6\le 12$

이어야 합니다. 4. 반대로 이 조건을 만족하는 6원소 부분집합은 B의 선호 순위를 적절히 잡아서 모두 실현할 수 있습니다. 5. 따라서 문제는 위 조건을 만족하는 6원소 부분집합의 수를 세는 것으로 바뀝니다. 6. 그 개수는 $211$입니다.

헷갈리기 쉬운 점

A가 원하는 선수를 고르는 문제가 아니라, 그때그때 남아 있는 최소 번호가 자동으로 들어간다는 점이 핵심입니다.

12. 연산의 합

문제 한눈에 보기

$1\square 1\square 1\square 1\square 1\square 1\square 1$의 6개 빈칸에 +, ^, &, |를 넣는 4096가지 경우의 값의 총합을 구하는 문제입니다.

답

$7936$

핵심 개념

현재 마지막 블록의 값이 $0$인지 $1$인지만 상태로 두는 DP가 가능합니다.

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

비트 연산 블록은 언제나 $0$ 또는 $1$만 만들고, +는 블록을 끝내는 역할만 하므로 상태 수가 매우 작습니다.

단계별 풀이

1. 왼쪽부터 식을 읽으면서 다음 4개 상태를 관리합니다.
2. $cnt0,cnt1$: 현재 마지막 블록 값이 $0$ 또는 $1$인 식의 개수
3. $sum0,sum1$: 그 식들에서 이미 끝난 블록 합의 총합
4. 처음 $1$ 하나만 있을 때는 $cnt1=1$, 나머지는 $0$입니다.
5. 새 $\square 1$을 붙일 때
6. +를 넣으면 현재 블록 값이 끝난 합에 더해지고, 새 블록 값은 $1$이 됩니다.
7. ^, &, | 중 하나를 넣으면 마지막 블록 값만 바뀝니다.
8. 이 갱신을 6번 반복하면 마지막 표는

$cnt0=1024,cnt1=3072,sum0=1024,sum1=3840$

이 됩니다. 9. 최종 총합은 끝난 블록 합에 마지막 블록 값을 더한 것이므로

$sum0+sum1+cnt1=1024+3840+3072=7936$

입니다.

헷갈리기 쉬운 점

+는 바로 계산하지 않고, “지금까지의 블록을 확정한다”는 관점으로 보면 DP가 훨씬 단순해집니다.

13. 트리 높이 줄이기

문제 한눈에 보기

트리의 높이를 10 이하로 만들기 위해 간선 길이를 최소 비용으로 줄이는 문제입니다.

답

최소 비용은 $5$입니다.

핵심 개념

가장 긴 루트-리프 경로들의 공통 간선을 먼저 줄이는 것이 최적입니다.

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

공통 간선 1을 줄이면 여러 longest path가 동시에 1씩 짧아집니다.

단계별 풀이

1. 현재 높이를 만드는 리프들을 찾습니다.
2. 그 경로들에 동시에 들어 있는 간선을 우선 줄입니다.
3. 남은 longest path에 대해서 같은 일을 반복합니다.
4. 해설 그림과 같이 줄이면 총 비용 $5$로 높이를 $10$까지 낮출 수 있습니다.

헷갈리기 쉬운 점

단순히 길이가 큰 간선을 줄이는 것이 아니라, 높이에 실제로 기여하는 간선을 골라야 합니다.

14. 사탕 놓기

문제 한눈에 보기

2차원 누적합 표 $S(i,j)$가 주어졌을 때 실제 0,1 배치를 복원하는 문제입니다.

답

행별로 쓰면 다음 배치가 됩니다.

$01111110$ $11000010$ $01101100$ $10100011$ $01001010$ $01100100$ $00010100$ $10001000$

핵심 개념

2차원 차분을 취하면 원래 배열이 복원됩니다.

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

누적합은 합치는 연산이고, 복원은 그 역연산인 차분입니다.

단계별 풀이

1. 각 칸의 실제 값 $a(i,j)$는

$S(i,j)-S(i-1,j)-S(i,j-1)+S(i-1,j-1)$

입니다. 2. 이 식을 64칸 모두에 적용하면 원래의 0,1 배치를 얻습니다. 3. 계산 결과는 위의 8줄 문자열과 같습니다.

헷갈리기 쉬운 점

왼쪽 위를 두 번 빼므로 마지막에 한 번 더해야 합니다.

15. 포크

문제 한눈에 보기

배열에서 $(i,i+2)$ 꼴의 두 원소만 함께 선택할 수 있을 때 최대합을 구하는 문제입니다.

답

해설의 최댓값은 $42$입니다.

핵심 개념

경로 그래프의 가중치 독립 간선 집합 문제와 같습니다.

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

$i$를 선택하면 $i+1$, $i+2$ 근처 선택이 막히므로 전형적인 1차원 DP가 됩니다.

단계별 풀이

1. $\mathrm{dp}[i]$를 $i$번째부터 끝까지 볼 때의 최대합으로 둡니다.
2. $i$를 건너뛰면 $\mathrm{dp}[i+1]$입니다.
3. $i$를 선택하면 $a_i+a_{i+2}+\mathrm{dp}[i+3]$입니다.
4. 따라서

$\mathrm{dp}[i]=\max (\mathrm{dp}[i+1],a_i+a_{i+2}+\mathrm{dp}[i+3])$

입니다. 5. 뒤에서부터 계산하면 최댓값 $42$를 얻습니다.

헷갈리기 쉬운 점

한 번 선택한 두 칸은 다시 쓸 수 없으므로 $i+2$도 함께 사라진다는 점을 놓치면 안 됩니다.

16. 실 태우기

문제 한눈에 보기

20개 지점 중 4개를 골라 길이 100인 실 전체가 다 타는 시간을 최소화하는 문제입니다.

답

한 가지 최적 선택은 $13,40,67,92$이고, 최적 시간은 $13.5$초입니다.

핵심 개념

1차원 k-center와 같은 형태입니다.

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

전체 시간은 각 불 사이 중 가장 늦게 도달하는 구간이 정하므로, 결국 최대 gap minimization입니다.

단계별 풀이

1. 선택한 점을 $x_1<x_2<x_3<x_4$라 하면, 전체 시간은

$\max (x_1,(x_2-x_1)/2,(x_3-x_2)/2,(x_4-x_3)/2,100-x_4)$

입니다. 2. 해설 선택 $13,40,67,92$에 대해 이 값은

$\max (13,13.5,13.5,12.5,8)=13.5$

입니다. 3. 따라서 최적 시간은 $13.5$초입니다.

헷갈리기 쉬운 점

중간 구간은 양쪽에서 동시에 타 들어가므로 절반을 봐야 합니다.

17. 올바른 괄호 문자열

문제 한눈에 보기

괄호 뒤집기 연산만으로 주어진 문자열을 올바른 괄호 문자열로 만드는 최소 횟수를 구하는 문제입니다.

답

최소 횟수는 $6$입니다.

핵심 개념

접두사 balance와 전체 balance를 분리해서 봅니다.

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

올바른 괄호 문자열 조건은 “모든 접두사 balance ≥ 0”과 “최종 balance = 0”의 두 조건으로 분해되기 때문입니다.

단계별 풀이

1. 왼쪽부터 보며 (는 $+1$, )는 $-1$로 둡니다.
2. 접두사 합이 음수가 되는 순간, 그 앞부분의 ) 하나는 반드시 (로 바뀌어야 합니다.
3. 이 과정을 greedy하게 적용하면 접두사 조건을 최소 비용으로 복구할 수 있습니다.
4. 이후 전체 balance가 양수면 뒤쪽의 (를 )로 바꾸어 총합을 0으로 맞춥니다.
5. 이 문자열의 최소 수정 횟수는 $6$입니다.

헷갈리기 쉬운 점

전체 개수만 맞추면 충분하지 않고, 모든 접두사도 함께 검사해야 합니다.

18. 버블 거울 정렬

문제 한눈에 보기

인접 두 카드를 swap하면서 동시에 뒤집는 연산으로, 숫자 오름차순과 전부 앞면 조건을 동시에 만족시키는 문제입니다.

답

한 가지 최적 답은 다음 $26$회입니다.

$8,7,2,1,5,4,3,2,6,5,4,3,9,8,7,6,5,4,11,10,6,7,9,8,9,11$

핵심 개념

정렬 상태와 뒤집힘 상태를 같이 관리해야 합니다.

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

숫자만 정렬되어도 카드가 뒷면으로 남아 있으면 실패이기 때문입니다.

단계별 풀이

1. 인접 swap은 버블 정렬과 같은 구조를 가집니다.
2. 하지만 각 swap이 두 카드의 방향도 바꾸므로, 위치와 방향이 동시에 상태가 됩니다.
3. 해설의 26회 수열은 이 두 조건을 동시에 만족하는 최적 예시입니다.

헷갈리기 쉬운 점

최종 배열이 오름차순이어도, 뒷면 카드가 남아 있으면 정답이 아닙니다.

19. 수식 최대화

문제 한눈에 보기

빼기 기호만 있는 수식에 괄호를 적절히 넣어 값을 최대화하는 문제입니다.

답

부분문제 1의 최댓값은 $34$, 부분문제 2의 최댓값은 $84$입니다.

해설의 한 가지 정답은 다음과 같습니다.

부분문제 1: $3-(1-4-1-5-9-2-6)-(-5)$

부분문제 2: $2-(-7-(-1-8-2-8)-(-1)-(-8-2)-(-8-4)-(-5)-(-9-4-5-2)-(-3-5))$

핵심 개념

빼기 사슬에서는 뒤쪽을 큰 음수 블록으로 묶을수록 유리합니다.

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

-( ... )는 괄호 내부의 전체 부호를 뒤집어 주므로, 여러 음수를 한꺼번에 플러스로 바꾸는 효과가 있기 때문입니다.

단계별 풀이

1. 괄호가 없으면 앞에서부터 순차적으로 빼기만 하게 됩니다.
2. 하지만 뒤쪽 항들을 적절히 묶으면 큰 음수 덩어리를 만들어 전체 값이 커집니다.
3. 해설의 괄호 배치를 적용하면 부분문제 1은 $34$, 부분문제 2는 $84$가 됩니다.

헷갈리기 쉬운 점

괄호를 많이 친다고 자동으로 좋아지지 않습니다. 실제 부호 반전을 따져야 합니다.

20. 동전 뒤집기

문제 한눈에 보기

한 동전을 고르면 그 동전을 포함해 같은 행 또는 같은 열의 11개 동전을 모두 뒤집습니다. 모든 동전을 앞면으로 만들면서 최소 행동 횟수를 구하는 문제입니다.

답

해설의 한 가지 최적 해는 $16$번이며, 예시 수열은 다음과 같습니다.

$(1,1),(2,1),(2,2),(4,2),(5,2),(4,3),(6,3),(5,4),(1,4),(1,5),(3,5),(3,6),(4,6),(6,6),(6,4),(4,4)$

핵심 개념

각 행동은 특정 행과 열의 상태를 동시에 바꾸는 연산입니다.

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

한 칸만 뒤집는 문제가 아니라 행과 열 전체에 파급되는 연산이므로, 지역적 판단만으로는 최소성을 보장할 수 없습니다.

단계별 풀이

1. 한 행동 $(i,j)$는 $(i,j)$를 포함하는 행과 열의 동전들을 한꺼번에 뒤집습니다.
2. 따라서 한 행동이 여러 칸에 동시에 영향을 주며, 전체 패턴을 맞추는 문제가 됩니다.
3. 해설은 위 16개 행동으로 모든 동전을 앞면으로 만들 수 있음을 보입니다.
4. 또한 $16$회가 최소 횟수인 최적해입니다.

헷갈리기 쉬운 점

같은 행 또는 같은 열에 있는 동전 11개를 모두 뒤집는 것이지, 선택한 한 칸만 뒤집는 것이 아닙니다.

개념 한눈에 보기

개념	나온 문제	기억할 말
LIFO	1	스택은 나중에 들어간 것이 먼저 나온다.
속력 비	2	같은 시간의 거리 비가 속력 비다.
역연산	3	뒤집기 연산은 역방향이 훨씬 쉽다.
사전식 rank	4	첫 자리부터 묶어 몇 번째인지 센다.
자릿수 가중합	5	$A+2B+3C$는 전체 자릿수다.
대칭 + 계수	6	$A=B$를 빼고 반으로 나눈다.
winning/losing	7	작은 잔여 구간으로 몰아넣는다.
역상 집합	8	$f^n(x)=0$은 0의 preimage를 반복한다.
mod 6 분류	9	평균이 홀수면 합은 $3\mathrm{mod}6$이다.
순서 보존	10	점프해도 개구리들의 순서는 안 바뀐다.
선택 규칙 상한	11	A의 i번째 픽에는 자연스러운 상한이 생긴다.
상태 DP	12	마지막 블록 값 0/1만 기억하면 된다.
longest path	13	여러 깊은 경로 공통 간선을 먼저 줄인다.
2차원 차분	14	누적합의 역연산으로 복원한다.
path DP	15	선택 / 비선택으로 최대합을 구한다.
1차원 k-center	16	최대 gap을 최소화한다.
balance	17	접두사와 전체 균형을 분리해 본다.
위치 + 방향	18	정렬 상태와 앞뒤 상태를 함께 맞춘다.
부호 반전	19	-(...)는 뒤쪽을 한 번 더 뒤집는다.
전역 토글	20	한 번의 행동이 행과 열 전체에 퍼진다.