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

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

이 문서는 2022 - 고등부 기출문제를 바탕으로, 고등학생 기준에서 다시 읽기 쉽게 정리한 학습용 풀이 노트입니다. 원본은 정답 PDF이므로, 계산형은 논리를 보강했고 구성형은 정답 절차를 왜 그렇게 잡는지 중심으로 설명했습니다.

1. 달리기

문제 한눈에 보기

다섯 사람의 순위 조건에서 3등이 누구인지 판정하는 문제입니다.

답

A

핵심 개념

전순서를 다 찾지 않아도, 위아래에 반드시 놓이는 사람 수만 세면 됩니다.

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

조건이 적은 순위 문제는 완전 탐색보다 “이 사람 위에 몇 명, 아래에 몇 명”이 더 직접적입니다.

단계별 풀이

1. B보다 순위가 낮은 사람은 없다이므로 B는 최하위 $5$등입니다.
2. E는 A와 B 사이에 있으므로 A보다 낮고 B보다는 높습니다.
3. 또 A는 C보다 낮고, D는 A보다 높습니다.
4. 따라서 A 위에 C, D 두 명, 아래에 E, B 두 명이 존재합니다.
5. 그래서 A는 정확히 $3$등입니다.

헷갈리기 쉬운 점

이 문제의 “순위가 낮다”는 더 못한 등수, 즉 숫자가 더 큰 쪽입니다.

2. 거스름돈

문제 한눈에 보기

7원, 9원, 11원 동전으로 $x$원 이상 모든 정수를 만들 수 있게 하는 최소 $x$를 구하는 문제입니다.

답

$27$

핵심 개념

가장 작은 동전이 7원이므로, 7개 연속 정수를 만들 수 있으면 그 이후는 전부 만들 수 있습니다.

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

무한히 많은 금액을 직접 검사할 수는 없습니다. 연속 구간을 하나 확보하는 것이 핵심입니다.

단계별 풀이

1. $27=9+9+9$
2. $28=7+7+7+7$
3. $29=11+9+9$
4. $30=7+7+7+9$
5. $31=11+11+9$, $32=11+7+7+7$, $33=11+11+11$
6. 따라서 $27$부터 $33$까지 7개 연속 정수를 만들 수 있습니다.
7. 여기에 7원 동전을 계속 더하면 $34$ 이상도 모두 표현됩니다.
8. 한편 $26$은 만들 수 없으므로 최소 시작점은 $27$입니다.

헷갈리기 쉬운 점

연속 구간의 시작 바로 아래 수가 표현 불가능한지도 확인해야 최소값이 됩니다.

3. 블록 쌓기

문제 한눈에 보기

세 직육면체 블록을 회전시켜 쌓을 때 가능한 최대 높이를 구하는 문제입니다.

답

$16$

핵심 개념

각 블록의 회전 상태를 “밑면 2변 + 높이”로 바꿔 보고, 밑면 포함관계를 만족하는 순서를 찾으면 됩니다.

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

직육면체를 통째로 보는 것보다 가능한 orientation들을 후보 상태로 나누는 편이 훨씬 간단합니다.

단계별 풀이

1. $(4,4,9)$는 높이 $4$, 밑면 $9\times 4$로 둘 수 있습니다.
2. $(2,5,8)$은 높이 $8$, 밑면 $5\times 2$로 둘 수 있습니다.
3. $(3,2,4)$는 높이 $4$, 밑면 $3\times 2$로 둘 수 있습니다.
4. 밑면 조건 $9\times 4\ge 5\times 2\ge 3\times 2$가 모두 성립합니다.
5. 따라서 총 높이 $4+8+4=16$이 가능합니다.
6. 이보다 높게 쌓으려면 가장 큰 높이값들을 모두 세워야 하는데, 그러면 밑면 포함관계가 깨져 불가능합니다.

헷갈리기 쉬운 점

한 블록의 가장 큰 변을 높이로 세우는 선택이 다른 블록의 배치를 막을 수 있습니다.

4. 점 잇기

문제 한눈에 보기

원 위의 8점을 4쌍으로 짝지어 선분으로 이을 때, 선분들이 서로 교차하지 않게 하는 방법 수를 구하는 문제입니다.

답

$14$

핵심 개념

교차하지 않는 완전 매칭의 개수는 Catalan 수입니다.

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

한 점이 누구와 연결되는지를 정하면 내부와 외부가 독립된 같은 형태의 작은 문제로 나뉩니다.

단계별 풀이

1. 8점을 원 둘레 순서대로 $1$부터 $8$이라 합시다.
2. 점 $1$이 어떤 점 2k와 연결되면, 그 안쪽과 바깥쪽은 각각 교차 없는 같은 문제로 분리됩니다.
3. 따라서 개수 $C_n$은
   $C_n=\sum C_i{C}_{n-1-i}$를 만족하는 Catalan 수가 됩니다.
4. $n=4$일 때
   $C_4=14$입니다.

헷갈리기 쉬운 점

단순한 짝짓기 수 $7\times 5\times 3\times 1$이 아닙니다. 교차 금지 조건 때문에 훨씬 작아집니다.

5. 구슬 뽑기

문제 한눈에 보기

4개의 상자 중 하나에서 구슬을 뽑았는데 첫 구슬이 검정이었습니다. 같은 상자에서 하나 더 뽑을 때 검정일 확률을 묻는 문제입니다.

답

$2/3$

핵심 개념

첫 구슬이 검정이라는 정보로 상자에 대한 확률이 바뀌므로, 조건부확률을 써야 합니다.

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

상자를 균등하게 고른 뒤 검정을 봤다면, 검정 구슬이 많은 상자일수록 더 가능성이 커집니다.

단계별 풀이

1. 그림의 상자 구성은 BBB, BBW, BWW, WWW 꼴로 읽을 수 있습니다.
2. 첫 구슬이 검정일 확률은 각각 $1$, $2/3$, $1/3$, $0$입니다.
3. 따라서 “검정을 봤다”는 조건 아래 상자 가중치는 3:2:1:0으로 바뀝니다.
4. 각 상자에서 두 번째도 검정일 확률은 $1$, $1/2$, $0$, $0$입니다.
5. 조건부확률은
   $(3\times 1+2\times 1/2+1\times 0)/(3+2+1)=4/6=2/3$입니다.

헷갈리기 쉬운 점

처음에 상자를 균등하게 골랐다고 해서, 첫 검정을 본 뒤에도 상자가 균등하다고 보면 안 됩니다.

6. 막대기 세우기

문제 한눈에 보기

높이 1부터 6까지 막대를 일렬로 세울 때, 왼쪽에서 3개, 오른쪽에서 2개가 보이게 하는 배열 수를 구하는 문제입니다.

답

$105$

핵심 개념

가장 큰 막대를 삽입하는 점화식
$f(n,l,r)=f(n-1,l-1,r)+f(n-1,l,r-1)+(n-2)f(n-1,l,r)$를 씁니다.

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

가장 큰 막대는 무조건 보이므로, 어디에 놓이는지가 왼쪽/오른쪽 가시 개수 변화를 정확히 결정합니다.

단계별 풀이

1. $f(n,l,r)$를 조건을 만족하는 배열 수라 둡니다.
2. 최대 높이 $n$이 맨 왼쪽이면 왼쪽에서 보이는 수가 하나 늘어 $f(n-1,l-1,r)$입니다.
3. 맨 오른쪽이면 $f(n-1,l,r-1)$입니다.
4. 가운데 $n-2$곳 중 하나면 가시 개수는 그대로여서 $(n-2)f(n-1,l,r)$입니다.
5. 따라서
   $f(6,3,2)=f(5,2,2)+f(5,3,1)+4f(5,3,2)$입니다.
6. 값은 각각 $22,11,18$이므로
   $22+11+4\times 18=105$입니다.

헷갈리기 쉬운 점

가장 큰 막대가 가운데 들어가면 양쪽 가시 개수가 둘 다 그대로라는 점이 핵심입니다.

7. 세 수의 곱

문제 한눈에 보기

수열에서 세 항을 골라 곱한 값의 최댓값을 구하는 문제입니다.

답

$252$

핵심 개념

최대 후보는 큰 양수 세 개와 작은 음수 두 개 + 큰 양수 하나입니다.

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

부호가 섞인 곱의 최대는 보통 “절댓값 큰 음수 둘”을 함께 써야 나옵니다.

단계별 풀이

1. 양수 셋 최대는 $6\times 5\times 4=120$입니다.
2. 음수 둘은 $-7,-6$이 가장 유리합니다.
3. 여기에 최대 양수 $6$을 곱하면 $(-7)(-6)6=252$입니다.
4. 따라서 최댓값은 $252$입니다.

헷갈리기 쉬운 점

가장 큰 수 세 개만 곱하는 방식은 음수 두 개의 효과를 놓칩니다.

8. 2310

문제 한눈에 보기

$a<b<c$, $abc=2310$인 양의 정수 삼쌍 개수를 묻는 문제입니다.

답

$40$

핵심 개념

$2310=2\cdot 3\cdot 5\cdot 7\cdot 11$은 서로 다른 소수 5개의 곱이므로, 각 소수를 $a,b,c$ 중 어디에 배정할지만 생각하면 됩니다.

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

소수 거듭제곱이 없어서 경우 분류가 매우 단순해집니다.

단계별 풀이

1. 순서를 고려한 삼쌍 $(a,b,c)$를 먼저 셉니다.
2. 다섯 소수 각각을 $a,b,c$ 중 하나에 배정하는 방법은 $3^5=243$입니다.
3. 이 중 두 수가 같아지는 경우는 $1,1,2310$의 순열 3개뿐입니다.
4. 따라서 서로 다른 세 수를 갖는 순서 있는 삼쌍은 $240$개입니다.
5. 각 증가삼쌍은 6개의 순열을 가지므로 정답은 $240/6=40$입니다.

헷갈리기 쉬운 점

소수를 배정하는 순간 곱이 정해지므로, 별도의 계수 분배는 없습니다.

9. 초콜릿

문제 한눈에 보기

14칸 초콜릿을 길이 2 또는 3의 묶음으로 잘라 판매할 때 얻는 금액의 최댓값을 구하는 문제입니다.

답

$25$

핵심 개념

각 위치까지의 최적값을 저장하는 1차원 DP로 해결할 수 있습니다.

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

구간 길이가 2, 3뿐이라서 앞에서부터 자르는 결정이 자연스러운 점화식으로 이어집니다.

단계별 풀이

1. $\mathrm{dp}[i]$를 앞에서 $i$칸까지 포장했을 때 최대 수익이라고 둡니다.
2. $i-2$칸 뒤에서 2칸 묶음을 자르거나, $i-3$칸 뒤에서 3칸 묶음을 자르는 두 경우를 비교합니다.
3. 단, 해당 묶음에 불량품이 2개 이상이면 그 전이는 금지합니다.
4. 그림의 불량 위치를 반영해 끝까지 계산하면 $\mathrm{dp}[14]=25$입니다.

헷갈리기 쉬운 점

3칸 정상 묶음의 단가가 가장 높아 보여도, 불량 위치 때문에 항상 최적은 아닙니다.

10. 순열 거듭제곱

문제 한눈에 보기

순열 $a$의 거듭제곱 $a^m$이 주어진 순열이 되게 하는 최소 $m$을 구하는 문제입니다.

답

$51$

핵심 개념

순열은 사이클 분해 후, 각 사이클에서 “몇 칸 회전했는가”를 합동식으로 쓰면 됩니다.

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

순열 합성은 전체로 보면 복잡하지만, 사이클 안에서는 단순한 회전입니다.

단계별 풀이

1. $a$를 사이클 분해하면 길이가 $4,5,2,1,3$인 사이클들로 나뉩니다.
2. 목표 순열을 같은 사이클 위에서 비교하면, 각 사이클에서 필요한 회전 수가 다음과 같이 나옵니다.
3. 길이 4 사이클에서는 $m\equiv 3(\mathrm{mod}4)$.
4. 길이 5, 2 사이클에서는 $m\equiv 1(\mathrm{mod}5)$, $m\equiv 1(\mathrm{mod}2)$.
5. 길이 3 사이클에서는 고정되어 있으므로 $m\equiv 0(\mathrm{mod}3)$입니다.
6. 이를 동시에 만족하는 최소 양의 정수는 $51$입니다.

헷갈리기 쉬운 점

순열 전체를 한 번에 거듭제곱하지 말고, 사이클마다 따로 보면 선형 합동식 문제가 됩니다.

11. 동전 게임

문제 한눈에 보기

동전을 1,2,3칸 옮기되 7의 배수 칸에는 놓지 못할 때, 목표 $k=22,24,32$에서의 승자를 판정하는 문제입니다.

답

영희, 철수, 영희

핵심 개념

뒤에서부터 winning/losing 상태를 분류하는 DP입니다.

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

현재 칸의 승패는 다음에 갈 수 있는 칸들의 승패만 보면 정해집니다.

단계별 풀이

1. $k$ 미만의 칸에 대해, 다음 한 번의 이동으로 이기는 칸이나 losing 칸으로 보낼 수 있으면 winning으로 둡니다.
2. 금지 칸인 7의 배수는 중간 도착지에서 제외합니다.
3. 이 DP를 적용하면
4. $k=22$에서는 시작칸 $0$이 winning,
5. $k=24$에서는 시작칸 $0$이 losing,
6. $k=32$에서는 다시 winning이 됩니다.
7. 따라서 승자는 영희, 철수, 영희입니다.

헷갈리기 쉬운 점

$k$ 이상에 처음 도달하는 순간 즉시 승리이므로, $k$ 이후 칸들은 따로 상태를 만들 필요가 없습니다.

12. 아이템 배치

문제 한눈에 보기

모든 시작-끝 경로가 정확히 한 개의 아이템만 지나가게 하는 아이템 배치 수를 세는 문제입니다.

답

$888$

핵심 개념

아이템 집합은 DAG의 모든 경로와 정확히 한 번 만나는 단절면이어야 합니다.

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

경로 수가 매우 많으므로, 각 경로를 직접 세는 방식은 불가능합니다.

단계별 풀이

1. 격자 이동을 DAG로 본 뒤, 시작에서 끝으로 가는 모든 경로를 생각합니다.
2. 아이템 칸들의 집합이 모든 경로와 정확히 한 번 교차해야 합니다.
3. 이런 집합은 서로 겹치지 않는 절단선들의 조합으로 이해할 수 있습니다.
4. 막힌 칸을 반영해 가능한 절단선을 DP로 세면 총 $888$가지가 나옵니다.

헷갈리기 쉬운 점

아이템을 하나도 못 줍는 경로도, 둘 이상 줍는 경로도 모두 불허입니다.

13. 한붓 그리기

문제 한눈에 보기

그래프에 간선 3개를 추가하여 오일러 회로를 만들고 실제 순회까지 제시하는 문제입니다.

답

정답 그림처럼 3개 간선을 추가하고, 예시 순서대로 돌면 된다.

핵심 개념

오일러 회로의 필요충분조건은 모든 정점 차수가 짝수인 연결 그래프라는 점입니다.

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

어떤 간선을 더해야 하는지 판단하는 기준이 차수의 짝홀뿐이기 때문입니다.

단계별 풀이

1. 원래 그래프의 홀수 차수 정점을 찾습니다.
2. 정답 그림처럼 3개 간선을 추가해 이 홀수 차수 정점들을 짝수로 바꿉니다.
3. 그러면 오일러 회로가 존재합니다.
4. PDF의 번호 기준 순회
   $1\to 2\to 4\to 6\to 7\to 3\to 5\to 8\to 6\to 5\to 1\to 4\to 3\to 1$
   는 모든 간선을 정확히 한 번씩 지나고 시작점으로 되돌아옵니다.

헷갈리기 쉬운 점

오일러 회로는 “간선”을 한 번씩 지나는 것이지 정점을 한 번씩 방문하는 것이 아닙니다.

14. 수열 만들기

문제 한눈에 보기

구간 덧셈만으로 목표 수열을 만드는 최소 작업 수를 구하는 문제입니다.

답

$10$번

핵심 개념

막대그래프를 최소 개수의 직사각형 합으로 분해하는 문제로 볼 수 있습니다.

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

구간에 상수 하나를 더하는 연산은 막대그래프에서 가로 띠 하나를 더하는 것과 같기 때문입니다.

단계별 풀이

1. 정답 자료의 10개 연산은
   $[1,12]+1$, $[1,3]+2$, $[8,12]+7$, $[10,12]+2$, $[5,6]+2$
2. 그리고 $[1,1]+2$, $[3,3]+3$, $[6,6]+3$, $[8,8]+7$, $[11,11]+2$입니다.
3. 이는 목표 막대그래프를 높이층별로 쪼갠 대표적인 분해입니다.
4. 이 10개를 적용하면 정확히 목표 수열이 됩니다.

헷갈리기 쉬운 점

연산에 음수를 쓸 수 없으므로, 한 번 지나치게 올리면 되돌릴 수 없습니다.

15. 트리 순회

문제 한눈에 보기

트리 위에서 18번 이하 이동으로 최대한 많은 서로 다른 정점을 방문하는 문제입니다.

답

14개 정점을 방문하는 경로가 정답

핵심 개념

한 가지를 깊게 탐색한 뒤, 되돌아오는 비용 대비 새 정점 수가 큰 가지부터 고르는 것이 핵심입니다.

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

트리에는 사이클이 없어서 다른 가지로 가려면 반드시 공통 조상으로 복귀해야 합니다.

단계별 풀이

1. 정답 경로는
   $4\to 3\to 2\to 5\to 6\to 7\to 6\to 5\to 8\to 9\to 8\to 11\to 15\to 11\to 8\to 17\to 22\to 24\to 25$
2. 이 경로는 총 18번 이동 안에서 정점 14개를 새로 방문합니다.
3. 큰 가지들을 이어 붙이되, 불필요한 왕복을 최소화한 경로라고 볼 수 있습니다.

헷갈리기 쉬운 점

중복 방문은 허용되지만 점수는 늘지 않으므로, 왕복은 “다른 가지로 넘어가기 위한 비용”일 뿐입니다.

16. 돌무더기

문제 한눈에 보기

두 바구니 A, B에서 서로 다른 규칙으로 돌을 가져가는 게임에서 선플레이어의 승리 전략을 찾는 문제입니다.

답

PDF의 전략대로 두면 승리한다.

핵심 개념

한 바구니를 먼저 소진해 게임을 단순화한 뒤, 남은 한 바구니에서 마지막 수를 맞추는 전략입니다.

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

두 자원을 동시에 제어하려고 하면 복잡도가 급격히 올라갑니다.

단계별 풀이

1. 정답 자료는 우선 B에서만 1개씩 가져가 B를 비우는 전략을 씁니다.
2. 그다음 A만 남으면, 현재 A의 짝홀에 맞춰 첫 수를 조정합니다.
3. 이후에는 상대가 A에서 1개밖에 못 가져가므로 마지막 돌을 내가 가져가게 흐름을 고정할 수 있습니다.

헷갈리기 쉬운 점

초반에 A까지 같이 건드리면 후반 짝홀 제어가 흐트러집니다.

17. 최대공약수

문제 한눈에 보기

주어진 여섯 연산만 써서 $(A,B)$를 $(G,0)$ 또는 $(0,G)$로 바꾸는 문제입니다.

답

이진 최대공약수 알고리즘을 따르면 된다.

핵심 개념

허용 연산이 정확히 Stein algorithm의 연산 집합과 일치합니다.

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

나누기 2와 빼기만으로 gcd를 보존하며 줄이는 알고리즘이 이미 존재합니다.

단계별 풀이

1. 공통 인수 $2^t$를 먼저 떼어 냅니다.
2. 이후 한쪽이 짝수면 그쪽만 $2$로 나누어 홀수로 만듭니다.
3. 둘 다 홀수이면 큰 쪽에서 작은 쪽을 뺍니다.
4. 이 과정을 반복하면 결국 두 수가 같은 홀수 $g$에 도달합니다.
5. 마지막에 한쪽에서 다른 쪽을 빼 $0$을 만든 뒤, 앞에서 떼어 둔 $2^t$를 다시 복원하면 $(G,0)$ 또는 $(0,G)$가 됩니다.

헷갈리기 쉬운 점

중간에 값이 커지거나 작아지는 것보다 중요한 것은 gcd가 보존되는지입니다.

18. 거짓말

문제 한눈에 보기

“같다/다르다” 질문을 각 캐릭터에게 한 번씩만 해서 참/거짓 속성을 모두 복원하는 문제입니다.

답

PDF의 질문 배치와 응답 해석으로 유일하게 복원 가능하다.

핵심 개념

질문 결과를 이진값 관계식으로 바꾸면, 전체 속성은 선형 제약계처럼 복원됩니다.

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

거짓말쟁이의 답도 결국 “참값을 뒤집은 값”으로 표현되므로, 모두 0/1 관계식으로 통일해서 볼 수 있습니다.

단계별 풀이

1. 각 캐릭터의 속성을 $0/1$ 변수로 둡니다.
2. 캐릭터 $i$의 답은 $a_i,b_i$의 속성이 같은지 다른지에 대한 관계식을 제공합니다.
3. 정답 자료의 질문 그래프는 이 식들이 충분히 독립적이도록 짜여 있습니다.
4. 그래서 답변이 한꺼번에 오면 전체 속성이 하나로 결정됩니다.

헷갈리기 쉬운 점

각 캐릭터는 자기 질문에 대해서만 참/거짓으로 답할 뿐, 다른 질문의 진위를 따로 판단하지 않습니다.

19. 격자판 장식하기

문제 한눈에 보기

격자판 꼭짓점에 세 가지 문양을 놓고, 빈 칸에는 대각선 방향도 골라서, 선으로 이어진 두 꼭짓점 문양이 모두 다르게 되게 만드는 문제입니다.

답

정답 그림처럼 문양과 대각선을 배치하면 된다.

핵심 개념

이 문제는 꼭짓점 3색칠과 대각선 선택을 동시에 맞추는 그래프 색칠 문제입니다.

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

대각선 방향을 정하면 인접 관계가 바뀌므로, 색칠과 선 선택을 별개가 아니라 한 번에 맞춰야 합니다.

단계별 풀이

1. 먼저 꼭짓점 문양을 3색칠 문제로 봅니다.
2. 이미 그어진 선이 강제하는 서로 다른 문양 조건을 만족하도록 기본 색을 정합니다.
3. 빈 칸의 대각선은 양 끝 꼭짓점 문양이 서로 달라지도록 방향을 고릅니다.
4. PDF의 해답 배치는 이 제약을 모두 만족하는 한 가지 완성 예입니다.

헷갈리기 쉬운 점

문양만 맞추고 대각선을 아무렇게나 채우면 새로 인접한 꼭짓점에서 충돌이 날 수 있습니다.

20. 괄호 문자열

문제 한눈에 보기

여러 구간이 모두 올바른 괄호 문자열이 되도록, 문자열의 두 문자를 최소 횟수로 서로 바꾸는 문제입니다.

답

각 부분 문제마다 최소 교환으로 구간들을 모두 균형 괄호 문자열로 만들면 된다.

핵심 개념

올바른 괄호 문자열은 전체 개수가 맞고, 모든 접두사에서 닫는 괄호가 더 많아지지 않아야 합니다.

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

단순히 (와 )의 개수만 맞춰서는 부족하고, 각 구간 내부의 prefix balance까지 맞춰야 하기 때문입니다.

단계별 풀이

1. 각 구간이 올바른 괄호 문자열이 되려면 그 구간의 길이는 짝수여야 하고 (, ) 개수가 같아야 합니다.
2. 또한 구간 안에서 왼쪽부터 볼 때 balance가 한 번도 음수가 되면 안 됩니다.
3. 교환 연산은 멀리 있는 괄호를 한 번에 옮길 수 있으므로, 부족한 여는 괄호/닫는 괄호를 필요한 구간으로 보내는 방식으로 최소 횟수를 맞춥니다.
4. PDF의 다섯 부분 문제는 각각 이런 원리로 최소 교환 수에 도달하면 정답 처리됩니다.

헷갈리기 쉬운 점

이번 연산은 인접 교환이 아니라 “임의의 두 문자 교환”입니다. 그래서 비용 계산이 더 작아질 수 있습니다.

개념 한눈에 보기

주제	해당 문제	한 줄 요약
관계 추론	1, 18	상대 위치나 참거짓 관계를 식으로 바꾸면 구조가 보인다.
수론	2, 8, 17	연속 표현 가능 구간, 소인수 배정, gcd 불변식을 이용한다.
조합/카탈란	4, 6	교차 금지나 가시 조건은 점화식으로 세는 것이 정석이다.
조건부확률	5	관측 정보가 들어오면 사후확률로 다시 가중해야 한다.
부호와 최적화	7, 9, 12	국소 선택보다 전체 최적 구조를 먼저 본다.
순열과 합동식	10	사이클 분해 후 회전량을 합동식으로 푼다.
게임 DP	11, 16	winning/losing 상태나 짝홀 제어로 승리 전략을 만든다.
그래프 오일러/색칠	13, 19	짝수 차수 조건, 3색칠 조건이 핵심 제약이다.
구간 연산	14, 20	수열과 괄호 모두 구간 구조를 맞추는 최소 조작 문제다.
트리 이동	15	새 정점 수 대비 왕복 비용이 큰 가지부터 고려한다.