2022 KOI 1차대회 고등부 문제 풀이

총평 및 문제 감상

이제 대학생이라 KOI에 참가하지 못하지만, 그래도 제가 한동안 정말 열심히 준비했던 대회인 만큼 풀이는 지속적으로 작성할 생각입니다.

• 2020 KOI 1차대회 고등부 문제 풀이
• 2021 KOI 1차대회 고등부 문제 풀이

작년에 이어서 올해도 1교시 난이도가 상승했습니다. 사고력 문제 유형(1~12번)의 난이도는 작년에 비해 조금 어려워졌고, 비버 챌린지 유형(13~20번)의 난이도가 많이 올랐습니다. 작년에 나온 Sprague-Grundy Theorem, Burnside’s Lemma와 같은 어려운 개념을 묻는 문제는 없지만, 풀이를 생각하는 난이도와 정답을 구하기 위해 필요한 계산량이 모두 증가했습니다. 앞으로도 계속 난이도가 올라간다면 시간 분배와 멘탈 관리가 중요해질 것 같습니다.

작년에 이어서 올해도 1-5, 1-13처럼 과거 지역 예선(2017년 이전 대회)에 자주 나왔던 유형의 문제가 다시 출제되었습니다. 이 사이트에서 과거 지역 예선 기출문제를, 여기에서 2014 ~ 2017년 수학 문제 풀이를 볼 수 있으니, 대회 준비할 때 참고하면 좋을 것 같습니다.

지난 2년 동안 KOI 1차 대회 풀이를 올리면서, 1교시 대비 방법에 대한 조언을 달라는 연락을 많이 받았습니다. 비버 챌린지 교재를 구매하거나 기출문제를 이용해 연습하는 분들을 많이 봤는데, 개인적으로 이 방법을 추천하진 않습니다. 지금까지의 KOI 기출문제를 보면 실제 비버 챌린지 문제와는 스타일이 조금 다르고, 오히려 실기 문제와 비슷한 문제가 많습니다. 컴퓨터가 해야 하는 계산을 손으로 해야 하는 부분만 빼면 크게 다르지 않습니다. 따라서 저는 비버 챌린지 기출로 대비하는 것보다는 온라인 저지 사이트에서 다양한 문제를 많이 풀어보는 것을 추천합니다.

2교시는 사람마다 난이도가 다르게 느껴질 것 같습니다. 특히 1교시 문제가 어려웠기 때문에 멘탈이 무너진 학생은 더 어렵게 느껴졌을 것이라 생각합니다. 작년/재작년 실기 문제와 유형이 조금 다른 점도 한몫한 것 같습니다.

저도 경험해 봐서 알지만, 멘탈이 약한 건 고치기 어렵습니다. 멘탈이 무너지지 않도록 여러 장치를 마련하는 것이 중요합니다. $x$분 이상 안 풀리면 다음 문제로 넘어가기, 대회 종료 $y$분 전부터는 부분 점수만 노리기, 모든 문제를 다 읽고 시작하기 같은 자신만의 규칙을 세워서 멘탈이 무너지지 않도록 전략을 미리 만드는 것을 추천합니다.

문제 유형

문제	유형	문제	유형	문제	유형	문제	유형
1번	위상정렬	2번	애드혹	3번	완전탐색	4번	DP
5번	확률	6번	DP	7번	그리디	8번	경우의 수
9번	DP	10번	정수론	11번	DP/게임 이론	12번	경우의 수
13번	그래프 이론	14번	그리디	15번	그래프 이론	16번	게임 이론
17번	정수론	18번	애드혹	19번	휴리스틱	20번	애드혹
실기 1번	정렬
실기 2번	그리디
실기 3번	세그먼트 트리 그리디

1-1. 달리기 (5점)

B는 꼴등이고, A는 C와 D보다 순위가 낮습니다. E는 B와 A 사이에 있어야 하므로 A, E, B가 각각 3등, 4등, 5등입니다.

1-2. 거스름돈 (5점)

현재 갖고 있는 동전으로 만들 수 있는 금액의 집합을 $S$를 알고 있을 때, $x$원 짜리 동전을 추가해서 만들 수 있는 금액의 집합 $S’$을 구하는 방법을 알아봅시다.
7원 짜리 동전만 이용해 만들 수 있는 집합 $S = \lbrace 7, 14, 21, 28, \cdots \rbrace$에 $x = 9$원 짜리 동전을 추가하는 경우를 예시로 설명하겠습니다.

먼저 1부터 적당한 수까지 한 줄에 $x(=9)$개씩 적은 다음, $S$에 포함된 원소를 표시합시다.

1 2 3 4 5 6 7

1 2 3 4 5 6 7(O) 8 9 10 11 12 13 14(O) 15 16 17 18 19 20 21(O) 22 23 24 25 26 27 28(O) 29 30 31 32 33 34 35(O) 36 37 38 39 40 41 42(O) 43 44 45 46 47 48 49(O) 50 51 52 53 54 55 56(O) 57 58 59 60 61 62 63(O)

한 줄에 $x(=9)$개씩 적었기 때문에, $S$에 속한 원소의 아래에 적힌 수들은 $x$원 짜리 동전을 몇 개 더 사용해서 만들 수 있습니다. 그러므로 표시된 원소의 밑에 위치한 수들을 표시합시다. $x, 2x, 3x, \cdots$도 표시하는 것을 잊지 마세요.
이 과정을 통해 7원 짜리와 9원 짜리 동전으로 48 이상의 모든 정수를 만들 수 있다는 것을 알 수 있습니다.

1 2 3 4 5 6 7

1 2 3 4 5 6 7(O) 8 9(O) 10 11 12 13 14(O) 15 16(X) 17 18(X) 19 20 21(O) 22 23(X) 24 25(X) 26 27(X) 28(O) 29 30(X) 31 32(X) 33 34(X) 35(O) 36(X) 37(X) 38 39(X) 40 41(X) 42(O) 43(X) 44(X) 45(X) 46(X) 47 48(X) 49(O) 50(X) 51(X) 52(X) 53(X) 54(X) 55(X) 56(O) 57(X) 58(X) 59(X) 60(X) 61(X) 62(X) 63(O)

동일한 방법으로 11원 동전을 추가할 수 있고, 정답은 27입니다.

1 2 3 4

1 2 3 4 5 6 7(O) 8 9(O) 10 11(O) 12 13 14(O) 15 16(O) 17 18(O) 19 20(X) 21(O) 22(X) 23(O) 24 25(O) 26 27(O) 28(O) 29(X) 30(O) 31(X) 32(O) 33(X) 34(O) 35(O) 36(O) 37(O) 38(X) 39(O) 40(X) 41(O) 42(O) 43(O) 44(O)

1-3. 블록 쌓기 (6점)

$L \leq W$인 경우만 생각해도 됩니다. 첫번째 블록은 $(2,5,8), (2,8,5), (5,8,2)$, 두번째 블록은 $(4,4,9), (4,9,4)$, 세번째 블록은 $(2,3,4), (2,4,3), (3,4,2)$가 가능합니다. 세 블록의 상태를 결정한 뒤($3\cdot2\cdot3=18$가지), 조건을 만족하도록 블록을 배열할 수 있는 경우 높이를 구하면 됩니다.
$(4,9,4), (2,5,8), (2,3,4)$를 차례로 쌓으면 높이를 16으로 만들 수 있습니다.

1-4. 점 잇기 (6점)

점이 $2k$개 있을 때의 정답을 $D(k)$라고 하고, 1번 점과 연결되는 점을 보면서 점화식을 계산합시다.

• 1번 점과 2번 점 연결: 3, 4, 5, 6, 7, 8번 점을 연결해야 함 → $D(4) \leftarrow D(3)$
• 1번 점과 4번 점 연결: 2, 3번 점을 연결하고 5, 6, 7, 8번 점을 연결해야 함 → $D(4) \leftarrow D(1) \times D(2)$
• 1번 점과 6번 점 연결: 2, 3, 4, 5번 점을 연결하고 7, 8번 점을 연결해야 함 → $D(4) \leftarrow D(2) \times D(1)$
• 1번 점과 8번 점 연결: 2, 3, 4, 5, 6, 7번 점을 연결해야 함 → $D(4) \leftarrow D(3)$

즉, $D(4) = 2\cdot D(3) + 2\cdot D(1)D(2)$입니다. $D(1) = 1, D(2) = 2$라는 것은 쉽게 알 수 있고, 동일한 방법으로 $D(3) = 5$를 계산한 다음 $D(4) = 14$를 계산할 수 있습니다.

1-5. 구슬 뽑기 (7점)

사건 $A$가 일어났다는 가정 하에 사건 $B$가 일어날 확률은 $P(B\vert A) = \frac{P(A\cap B)}{P(A)}$로 계산할 수 있습니다.
4개의 상자 중 한 곳에서 무작위로 구슬을 1개 뽑을 때 검은색 구슬을 뽑을 확률은 $\frac{6}{12}$이고, 구슬을 2개 뽑을 때 모두 검은색 구슬일 확률은 $\frac{4}{12}$입니다. 그러므로 정답은 $\frac{2}{3}$입니다.

1-6. 막대기 세우기 (7점)

BOJ 1328 고층 빌딩과 동일한 문제입니다.
왼쪽에서 $l$개, 오른쪽에서 $r$개의 막대가 보이도록 $i$개의 막대를 배치하는 경우의 수를 $D(i,l,r)$이라고 정의합시다. 높이가 가장 낮은 막대를 추가하는 과정을 통해 점화식을 세울 수 있습니다.

• 가장 낮은 막대를 가장 왼쪽에 추가하는 경우: 왼쪽에서 보이는 막대의 개수 1 증가 → $D(i,l,r) \leftarrow D(i-1,l-1,r)$
• 가장 낮은 막대를 가장 오른쪽에 추가하는 경우: 오른쪽에서 보이는 막대의 개수 1 증가 → $D(i,l,r) \leftarrow D(i-1,l,r-1)$
• 나머지 경우($i-2$ 가지): 다른 막대에 가려지기 때문에 변하지 않음 → $D(i,l,r) \leftarrow (i-2)\cdot D(i-1,l,r)$

점화식은 $D(i,l,r) = D(i-1,l-1,r) + D(i-1,l,r-1) + (i-2)\cdot D(i-1,l,r)$이고, 직접 $D(6,3,2)=105$를 계산하면 됩니다.

1-7. 세 수의 곱 (9점)

세 수를 곱해서 양수가 나오는 경우는 양수를 3개 곱하는 경우와 양수 1개, 음수 2개를 곱하는 경우밖에 없습니다. 각 경우에 대해 절댓값이 큰 수를 선택해 곱하면 최댓값을 얻을 수 있습니다. 양수 3개를 곱하는 경우의 최댓값은 $6\cdot5\cdot4=120$이고, 양수 1개와 음수 2개를 곱하는 경우의 최댓값은 $6\cdot(-6)\cdot(-7)=252$입니다.

1-8. 2310 (9점)

$2310 = 2\times3\times5\times7\times11$입니다. 그러므로 이 문제는 5개의 소인수를 적당히 세 곳으로 분배하는 경우의 수를 세는 문제입니다.
$a, b, c$ 중 1이 2번 또는 3번 등장하는 경우를 제외하면 같은 값이 나올 일이 없기 때문에, 단순히 분배하는 경우의 수만 세도 정답을 구할 수 있습니다.

• 소인수를 0 / 1 / 4로 분해하는 경우 : $5!/4! = 5$
• 소인수를 0 / 2 / 3으로 분배하는 경우 : $5!/2!/3! = 10$
• 소인수를 1 / 1 / 3으로 분배하는 경우 : $5!/3! = 20$, 이때 소인수가 1개인 자리가 2개 있으므로 2로 나눠야 함 $\rightarrow 10$
• 소인수를 1 / 2 / 2로 분배하는 경우 : $5!/2!/2! = 30$, 이때 소인수가 2개인 자리가 2개 있으므로 2로 나눠야 함 $\rightarrow 15$
• $5 + 10 + 10 + 15 = 40$

1-9. 초콜릿 (10점)

1번 칸부터 $i$번 칸까지만 포장했을 때의 최대 가격을 $D(i)$라고 합시다. $l$번 칸부터 $r$번 칸까지 한 묶음으로 포장했을 때의 가격을 $C(l,r)$라고 하면 $D(i) = \max\lbrace D(j-1) + C(j,i)\rbrace$입니다. 점화식을 직접 계산하면 문제를 해결할 수 있습니다.
$D = \lbrace -\infty,4,5,7,9,10,12,13,15,17,20,20,22,25 \rbrace$ (1-based)이므로 정답은 $D(14) = 25$입니다.

1-10. 순열 거듭제곱 (10점)

순열 $a = [10,1,15,2,9,6,13,14,5,4,8,7,3,11,12]$의 거듭제곱 $a^k$에서 각 칸의 값이 어떻게 변하는지 살펴봅시다.

• $a[1]$은 $k$가 증가함에 따라 $10\rightarrow4\rightarrow2\rightarrow1\rightarrow10\rightarrow\cdots$을 반복합니다.
• $a[3]$은 $k$가 증가함에 따라 $15\rightarrow12\rightarrow7\rightarrow13\rightarrow3\rightarrow15\rightarrow\cdots$를 반복합니다.
• $a[5]$는 $k$가 증가함에 따라 $9\rightarrow5\rightarrow9\rightarrow\cdots$를 반복합니다.
• $a[6]$은 $k$에 관계 없이 $6$입니다.
• $a[8]$은 $k$가 증가함에 따라 $14\rightarrow11\rightarrow8\rightarrow14\rightarrow\cdots$를 반복합니다.

순열을 사이클로 분할하면, $a^m = [2,4,15,10,9,6,13,8,5,1,11,7,3,14,12]$가 되는 $m$에 대한 조건을 얻을 수 있습니다.
먼저, $a[1]$의 값을 통해 $m$을 4로 나눈 나머지가 3이라는 사실을 알 수 있습니다. 동일한 방식으로 $m$을 5로 나눈 나머지는 1, $m$을 2로 나눈 나머지는 1, $m$을 3으로 나눈 나머지는 0이라는 사실을 알 수 있습니다.

4가지 조건을 만족하는 가장 작은 $m$은 중국인의 나머지 정리를 이용해 구할 수 있습니다. 또는 정답이 $4, 5, 2, 3$의 최소공배수 이하라는 사실을 이용해 $60$까지의 모든 수를 확인해보는 방법도 가능합니다. 정답은 51입니다.

1-11. 동전 게임 (15점)

자신의 플레이어가 턴을 시작할 시점에 동전이 $i$에 위치했을 때 무조건 승리할 수 있다면 $D(i) = 1$, 그렇지 않으면 $D(i) = 0$으로 정의합시다. $D(k-1) = D(k-2) = D(k-3) = 1$입니다.
만약 동전을 $i$에서 $D(j) = 0$인 $j$로 보낼 수 있다면 $D(i) = 1$이고, 어떠한 경우에도 $D(j) = 0$인 $j$로 보낼 수 없으면 $D(i) = 0$입니다. $D(0) = 1$이면 먼저 시작하는 사람인 영희가 이기고, $D(0) = 0$이면 철수가 이깁니다.

베스킨라빈스 31 게임의 필승법을 생각하면 $k = 22, 24$인 경우는 바로 해결할 수 있습니다. $k = 32$인 경우에는 28이 7의 배수이기 때문에 베스킨라빈스 31 게임의 필승법을 그대로 적용하지 못하므로 직접 계산해야 합니다.
$k = 32$인 경우, $D = \lbrace1,1,0,1,1,1,0,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0,0,1,1,1,0\rbrace$ (0-based)입니다.

1-12. 아이템 배치 (15점)

출발 지점에서 도착 지점까지 가는 경로는 크게 위, 아래, 가운데로 가는 세 가지로 구분할 수 있습니다.

각 경로마다 항상 통과해야 하는 칸을 A, B, C, 어떤 경로로 이동하더라도 절대 통과하지 않는 칸을 ?로 표시해 보겠습니다. 빨간색으로 적혀있는 A와 B는 가운데로 지나는 경로에도 간섭하기 때문에 주의해서 계산해야 합니다.
?로 표시된 두 칸은 통과할 일이 없기 때문에 계산에서 제외한 뒤, 최종 결과에 $2^2 = 4$를 곱하도록 합시다.

위/아래/가운데로 가는 경로에서 각각 서로 다른 아이템을 먹도록 하는 경우부터 고려합시다. 즉, 아래 그림에서 회색으로 칠해지지 않은 칸에만 아이템을 배치하겠습니다.
무조건 지나야 하는 한 칸에 아이템을 배치할 수도 있고, 혹은 대각선 방향으로 아이템을 배치해서 그중 정확히 하나를 가져가도록 할 수도 있습니다. 위로 가는 경로에서 6가지, 아래로 가는 경로에서 6가지, 가운데로 가는 경로에서 6가지를 선택할 수 있으므로, 이 경우에는 $6\times6\times6=216$가지를 선택할 수 있습니다.

이제, 세 종류의 경로를 한 번에 커버하는 경우를 고려합시다. 즉, 위 그림에서 회색으로 칠해진 칸을 포함하도록 몇 개의 아이템을 배치할 것입니다.
이 경우는 아래 그림처럼 6가지의 방법이 있습니다.

?로 표시된 칸을 고려하지 않은 경우의 수는 $216 + 6 = 222$가지입니다. 여기에 ?로 표시된 두 칸에 아이템을 배치하는 방법의 수 $2^2 = 4$를 곱하면 $222\times4=888$을 얻을 수 있습니다.

1-13. 한붓 그리기 (8점)

한붓 그리기가 가능할 필요 충분 조건은 차수가 홀수인 정점이 0개 또는 2개 존재하는 것입니다. 주어진 그래프의 각 정점의 차수는 각각 $1, 1, 2, 3, 3, 3, 3, 4$입니다. 차수가 홀수인 정점이 6개이므로, 이들을 2개씩 간선으로 짝을 지으면 3개의 간선을 이용해 한붓 그리기가 가능하도록 만들 수 있습니다.

여담으로, 올림피아드의 출제 범위를 벗어나는 이야기지만 가중치 그래프에서 이 문제는 $O(\vert V\vert^3)$에 해결할 수 있습니다. 이 글의 1. Chinese Postperson Problem 문단을 참고하세요.

1-14. 수열 만들기 (8점)

0이 등장하지 않는 가장 긴 구간을 찾은 다음, 뺄 수 있는 가장 큰 값(구간의 최솟값)을 빼는 것을 반복하는 것이 최적입니다. 10번 만에 문제에서 제시한 수열을 만들 수 있습니다.

1-15. 트리 순회 (8점)

어느 한 곳으로 들어갔다가 다시 나오는 것은 되도록 피하는 것이 좋습니다. 그러므로, 기본적으로 트리의 지름을 따라가면서 남는 이동 횟수를 적당히 소모하는 것이 최적입니다.
트리의 지름을 따라 이동하면 8번의 이동으로 9개의 정점을 방문하게 되고, 중간에 10번 더 이동할 수 있습니다. $n$개의 정점을 추가로 방문하기 위해 들어갔다 나오는데 $2n$번의 이동이 필요하므로 5개의 정점을 추가로 방문하면 문제를 해결할 수 있습니다.

1-16. 돌무더기 (12점)

플레이어는 바구니 A에서 1개 또는 2개 가져가거나, B에서 1개를 가져갈 수 있습니다. 반대로 컴퓨터는 A에서 1개를 가져가거나, B에서 1개 또는 2개 가져갈 수 있습니다.
만약 바구니 B를 비울 수 있다면, 컴퓨터는 바구니 A에서 1개씩만 가져갈 수 있으므로 홀짝을 적당히 조절해서 항상 A가 이기도록 만들 수 있습니다.

일단 바구니 B에서 돌을 1개씩 가져가서 바구니 B를 비워냅시다. 만약 컴퓨터가 바구니 A에서 하나씩 가져가서 A가 한 턴 먼저 비워진다면, 플레이어는 바구니 B에 남은 마지막 돌을 가져가는 것으로 승리할 수 있습니다.

그렇지 않은 경우, 즉 바구니 A에만 돌이 남게 된 상황을 생각합시다. 바구니 B가 비워진 다음 처음으로 플레이어의 턴이 돌아오면 바구니 A에는 1개 이상의 돌이 있습니다. 만약 짝수 개의 돌이 있으면 2개를 가져가고 홀수 개의 돌이 있다면 1개를 가져가서 돌을 짝수 개로 만듭시다.
컴퓨터가 돌을 가져가면 홀수 개가 되고, 그 다음부터는 항상 1개씩 가져가면 플레이어가 마지막 돌을 가져가서 승리할 수 있습니다.

상대방의 선택지를 제한하고, 상대방의 전략에 맞춰 간다는 생각으로 전략을 세우면 됩니다.

1-17. 최대공약수 (12점)

$a, b$의 최대공약수 $\gcd(a,b)$에 대해 아래 4가지가 성립합니다.

• $\gcd(a,0) = a$
• $a \geq b$이면 $\gcd(a,b) = \gcd(a-b, b)$
• $\gcd(2a,2b) = 2\times\gcd(a,b)$
• $a$가 홀수면 $\gcd(a,2b) = \gcd(a,b)$

이 성질들을 이용해 최대공약수를 구하는 방법을 알아봅시다.

1. 먼저 $a, b$가 모두 짝수라면 둘 중 하나 이상이 홀수가 될 때까지 2로 나누고, 나눈 횟수 $k$를 기억합시다.
   • 최대 $O(\log \min(a,b))$번의 나눗셈을 수행합니다.
   • $a, b$를 2로 여러 번 나눠서 얻은 값을 $a’, b’$이라고 하면, $\gcd(a,b) = 2^k\gcd(a’,b’)$입니다.
2. $a, b$ 중 하나 이상은 홀수입니다. 둘 중 짝수가 있다면 홀수가 될 때까지 2로 나눕니다.
   • 이 과정에서 최대공약수는 변하지 않습니다.
3. 두 수가 모두 홀수가 되었다면 큰 수에서 작은 수를 뺍니다.
   • 이 과정에서 최대공약수는 변하지 않습니다.
4. 0이 나올 때까지 2~3번 과정을 반복합니다.
   • 이 과정은 최대 $O(\log \max(a,b))$번 반복합니다.
5. 둘 중 0이 아닌 값에 $2^k$를 곱한 결과가 최대공약수입니다.

이 과정을 직접 수행하면 주어진 연산만 사용해서 문제를 해결할 수 있습니다. 이 방법은 Binary GCD Algorithm 또는 Stein’s Algorithm이라는 이름으로 알려져 있습니다.

1-18. 거짓말 (13점)

만약 두 사람 $A, B$의 속성만 알아낼 수 있다면, 다른 사람들의 속성는 $A \neq B$ 질문의 결과로 알아낼 수 있습니다. 두 사람의 속성을 특정하는 방법을 찾아봅시다.

$a, b$에게 동일하게 $A \neq B$인지 물어봅시다. 만약 $a$와 $b$의 답변이 동일하면 $a = b$이고, 둘의 답변이 다르면 $a\neq b$입니다.
이제 $A, B$에게 $a\neq b$인지 물어봅시다. 우리는 이 질문의 정답을 알고 있기 때문에 $A$와 $B$의 속성을 알아낼 수 있습니다. 그러므로 4명만 있어도 두 사람 $A, B$의 속성을 알아낼 수 있습니다.

1, 2번 사람에게 $3\neq 4$인지 물어보고, 다른 모든 사람에게 $1\neq 2$인지 물어본 다음, 위에서 설명한 방법에서 $A=1,B=2,a=3,b=4$를 대입해서 정답을 구하면 됩니다.

1-19. 격자판 장식하기 (15점)

삼각형의 세 꼭짓점 중 두 개의 문양이 결정되었다면 나머지 하나는 바로 결정할 수 있습니다. 왼쪽 아래에 있는 삼각형부터 시작해 봅시다.

J 영역의 간선을 역슬래시로 놓고 문양을 채워 봅시다. G 영역에서 간선을 만들 수 없기 때문에 J 영역에 역슬래시 모양의 간선을 넣으면 안 된다는 것을 알 수 있습니다.

J 영역에 슬래시 모양의 간선을 넣고 문양을 채웁시다. G 영역의 간선도 함께 채울 수 있습니다.

이제 A 영역의 간선을 결정해 봅시다. 일단 슬래시 모양의 간선을 넣어보겠습니다. A,B,D,H,K,I,L,E,F 영역의 간선을 순서대로 결정할 수 있고, 빨간색으로 표시한 부분에서 조건을 만족하지 않는 간선이 등장합니다.

A 영역에 역슬래시 모양의 간선을 넣읍시다. A,B,D,H,K,I,L,E,F,C 영역의 간선을 순서대로 결정할 수 있고, 문제에서 요구하는 정답을 얻을 수 있습니다.

1-20. 괄호 문자열 (20점)

만들고자 하는 괄호 문자열을 고정하면, 이를 만드는데 필요한 교환 횟수는 (원본 문자열과 목표 문자열의 문자가 다른 위치의 수) / 2를 올림한 값 입니다. 교환할 때마다 2글자가 맞춰지기 때문에 (문자가 다른 위치의 수)를 2로 나눈 나머지가 최소 횟수입니다. 만약 그러한 위치의 개수가 홀수인 경우, 구간에 포함되지 않은 문자 하나를 바꿔야 하기 때문에 (위치의 개수 + 1) / 2, 즉 위치의 개수를 2로 나눈 나머지를 올림한 값이 정답이 됩니다.

만약 구간 $[s, e]$가 $[s’,e’]$을 포함한다면, $[s’,e’]$과 $[s,e]\setminus[s’,e’]$가 각각 올바른 괄호 문자열이 되도록 만들면 됩니다. 만약 구간 $[s,e]$와 $[s’,e’]$이 겹치는 부분이 있다면($s \leq s’ \leq e \leq e’$이라고 가정), $[s,s’-1], [s’,e], [e+1,e’]$이 각각 올바른 괄호 문자열이 되도록 만들면 됩니다.
겹치는 구간들을 잘라내면 고려해야 하는 구간의 크기를 줄일 수 있습니다.

각 구간마다 독립적으로 목표 문자열을 만들어도 됩니다. 구간의 크기가 충분히 작기 때문에 “원본 문자열과 목표 문자열이 다른 위치의 수”를 최소화하는 목표 문자열은 직접 구할 수 있습니다.

아래 텍스트는 제가 구한 답안입니다. 첫째 줄은 원본 문자열, 둘째 줄부터는 각 구간의 목표 문자열입니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

# 1 )()())(()((()) (()) 2 ()() 2 ()(()) 2 (2+2+2)/2 = 3 # 2 ))))(())))((((()((() (())------ 2 ((()))---------- 1 ((((())))) 3 (2+1+3)/2 = 3 # 3 (()()()))()(())( ((--------)) 1 ((----)) 2 (()) 1 (--) 1 () 1 (1+2+1+1+1)/3 = 3 # 4 )))))))))))))((((((((((((( (------------------------) 2 ()(------)() 3 ((())) 3 --(----------) 1 ()()-- 2 ()()() 3 (2+3+3+1+2+3)/2 = 7 # 5 )()()))))())(()((()()))(((((() ()(--------((------))------) 1 (())(()) 3 ((())) 3 ((())) 4 (1+3+3+4)/2 = 5.5 -> 6 (마지막 글자를 '('로 바꿔야 함)

2-1. 피하자

두 가지 풀이가 있고, 두 풀이 모두 좋은 풀이이므로 공부하는 것을 권장합니다.

풀이 1 - 공식 풀이와 동일

주어진 원소의 값이 아닌 2로 나눈 나머지만 고려해도 충분합니다. 그러므로 0과 1로만 구성된 배열이라고 생각합시다.

홀수와 짝수가 인접한 경우가 0번 등장하는 경우는 모든 원소가 0이거나 모든 원소가 1인 경우밖에 없습니다. 1번 등장하는 경우는 앞에 0이 모두 등장한 다음 뒤에 1이 등장하는 경우와 그 반대의 경우가 있습니다. 결국, 이 문제는 배열을 $[0,0,\cdots,0,1,1,\cdots,1]$ 또는 $[1,1,\cdots,1,0,0,\cdots,0]$ 꼴로 만드는 문제라고 생각할 수 있고, 배열을 오름차순 또는 내림차순으로 정렬하는 문제가 됩니다.

오름차순으로 정렬하는 경우만 생각합시다. 내림차순으로 정렬하는 것은 동일한 방법으로 할 수 있습니다.
인접한 원소를 교환하면서 배열을 오름차순으로 정렬할 때, 필요한 교환의 최소 횟수는 $i < j \text{ and } A_i > A_j$를 만족하는 순서쌍 $(i, j)$의 개수와 같습니다. 배열의 크기가 최대 $10^6$으로 매우 크기 때문에 모든 $(i,j)$ 쌍을 확인하는 것으로는 문제를 해결할 수 없습니다.

이 문제에서 $i < j \text{ and } A_i > A_j$이면 $A_i = 1, A_j = 0$를 만족하기 때문에, 조건을 만족하는 순서쌍 $(i,j)$의 개수는 $A_j = 0$인 $j$에 대해 자신보다 앞에 있는 $1$의 개수의 합이라고 생각할 수 있습니다. 이는 지금까지 등장한 1의 개수를 관리하면 $O(N)$에 계산할 수 있습니다.
그러므로 오름차순으로 정렬하는데 필요한 필요한 교환 횟수를 $O(N)$ 시간에 구할 수 있고, 동일한 방법으로 내림차순 정렬도 $O(N)$ 시간에 처리할 수 있습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include <bits/stdc++.h> using namespace std; int N, A[1010101]; long long R=1e18; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N; for(int i=1; i<=N; i++) cin >> A[i], A[i] %= 2; for(int iter=0; iter<2; iter++){ long long cnt = 0, acc = 0; for(int i=1; i<=N; i++){ if(A[i] == iter) acc += 1; else cnt += acc; } R = min(R, cnt); } cout << R; }

풀이 2 - 별해

$i$번째에 있는 수를 $j$번째로 옮기기 위해서는 인접한 원소를 $\vert i-j\vert$번 교환해야 합니다. 같은 값을 가진 원소끼리 서로 역전하면 항상 손해이기 때문에 역전하지 않는 경우, 즉 서로의 상대적인 순서를 유지하는 경우만 생각해도 됩니다.

입력에서 0이 등장한 위치를 $X_1, X_2, \cdots, X_k$, 1이 등장한 위치를 $Y_1, Y_2, \cdots, Y_{N-k}$라고 합시다. 배열을 오름차순으로 정렬하기 위해서는 $X_i$는 $i$번째로 이동해야 하고, $Y_i$는 $k+i$로 이동해야 합니다. 그러므로 각 원소들의 이동 거리의 합은 $\sum \vert X_i - i\vert + \sum \vert Y_i-(k+1)\vert$가 됩니다.

이때 인접한 두 원소를 교환할 때마다 원소 2개의 위치가 1씩 바뀌기 때문에, 위에서 계산한 이동 거리의 합을 2로 나눈 값이 문제의 정답이 됩니다. 이 방법을 사용해도 $O(N)$ 시간에 해결할 수 있습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <bits/stdc++.h> using namespace std; int N, A[1010101]; long long R=1e18; vector<int> V[2]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N; for(int i=1; i<=N; i++) cin >> A[i], V[A[i]%2].push_back(i); for(int iter=0; iter<2; iter++){ long long now = 0, cnt = 0; for(int i=0; i<2; i++){ for(auto j : V[i]) now += abs(++cnt - j); } R = min(R, now); swap(V[0], V[1]); } cout << R / 2; }

2-2. ABBC

세 가지 풀이가 있습니다. 풀이 3에 사용되는 개념은 올림피아드에 자주 등장하는 주제는 아니지만, 알고리즘을 깊게 공부하고자 하는 학생이라면 공부하는 것을 추천합니다.

풀이 1 - $O(N)$ 풀이

$B$는 $A$와 매칭될 수도 있고 $C$와 매칭될 수도 있습니다. 이때 $A$와 매칭할 때 사용할 $B$는 뒤에 있는 것부터 사용하는 것이 좋고, $C$와 매칭할 때 사용할 $B$는 앞에 있는 것부터 사용하는 것이 좋습니다.
일단 지금은 $C$를 생각하지 말고, 뒤에 있는 $B$부터 차례로 보면서 자신보다 앞에 있는 가장 가까운 $A$와 매칭합시다. 이렇게 하면 $A-B$ 매칭의 개수가 최대가 되고, 이 과정은 투 포인터를 이용해 $O(N)$에 할 수 있습니다. 이후 $A$와 매칭이 안 된 $B$를 차례로 보면서 자신보다 뒤에 있는 $C$와 매칭하면 됩니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

#include <bits/stdc++.h> using namespace std; int N; string S; vector<int> V[3]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> S; N = S.size(); for(int i=0; i<N; i++) V[S[i]-'A'].push_back(i); int res = 0; for(int i=(int)V[1].size()-1, j=(int)V[0].size()-1; i>=0; i--){ while(j >= 0 && V[1][i] < V[0][j]) j--; if(j >= 0) res++, j--, V[1].pop_back(); } for(int i=0, j=0; i<V[1].size(); i++){ while(j < V[2].size() && V[2][j] < V[1][i]) j++; if(j < V[2].size()) res++, j++; } cout << res; }

풀이 2 - $O(N \log N)$ 풀이

뒤에 있는 $a$개의 $B$는 $A$와 매칭할 때만 사용하고, 나머지 앞에 있는 $c=N-a$개의 $B$는 $C$와 매칭할 때만 사용한다고 합시다. $a$가 고정되어 있으면 풀이 1처럼 투 포인터를 이용해 $O(N)$에 최대 매칭을 구할 수 있습니다.
$a$가 고정되었을 때의 최대 매칭의 크기를 $f(a)$라고 하면, $f(a)$는 증가하다가 극댓값을 찍고 감소하는 형태임을 알 수 있습니다. 그러므로 삼분 탐색을 이용해 $O(N \log N)$에 문제를 해결할 수도 있습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <bits/stdc++.h> using namespace std; int N; string S; vector<int> V[3]; int f(int a){ vector<int> A, C; int c = V[1].size() - a; for(int i=0; i<c; i++) C.push_back(V[1][i]); for(int i=c; i<a+c; i++) A.push_back(V[1][i]); int res = 0; for(int i=0, j=0; i<a; i++){ if(j < V[0].size() && V[0][j] < A[i]) res++, j++; } for(int i=c-1, j=(int)V[2].size()-1; i>=0; i--){ if(j >= 0 && C[i] < V[2][j]) res++, j--; } return res; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> S; N = S.size(); for(int i=0; i<N; i++) V[S[i]-'A'].push_back(i); int l = 0, r = V[1].size(); while(l + 3 <= r){ int m1 = (l + l + r) / 3, m2 = (l + r + r) / 3; if(f(m1) < f(m2)) l = m1; else r = m2; } int res = 0; for(int i=l; i<=r; i++) res = max(res, f(i)); cout << res; }

풀이 3 - 별해

시간 복잡도를 생각하지 않으면, 이 문제는 이분 매칭을 이용해 정답을 구할 수 있습니다. 각 문자를 정점으로 생각한 다음, 각 $B$마다 자신과 매칭 가능한 $A, C$들을 연결하면 정점이 $O(N)$개, 간선이 $O(N^2)$개 있는 이분 그래프를 만들 수 있습니다. Ford-Fulkerson Method을 기반으로 한 $O(VE)$ 알고리즘을 사용하면 $O(N^3)$, Hopcroft-Karp Algorithm을 이용하면 $O(E\sqrt V) = O(N^{2.5})$에 정답을 구할 수 있습니다. 이 풀이를 발전시켜 봅시다.

그래프에서 각 $B$와 연결되는 $A$와 $C$는 각각 연속한 구간으로 나타낼 수 있습니다. 이렇게 어떤 정점을 구간에 속한 모든 정점과 연결하는 것은 세그먼트 트리를 이용해 최적화 할 수 있다는 것이 잘 알려져 있습니다. 잘 알려져 있지 않은 것 같다면 링크된 글로 이동해 공부해 보세요.
세그먼트 트리를 이용하면 정점 $O(N)$개, 간선 $O(N \log N)$개로 구성된 그래프를 얻을 수 있습니다. 이 그래프에서 최대 유량을 구하면 되고, Dinic’s Algorithm을 이용해 최대 유량을 구하면 100점을 받을 수 있습니다. 자세한 그래프 모델링은 아래 코드를 참고하세요.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

#include <bits/stdc++.h> using namespace std; int SZ = 1; vector<int> GetRange(int l, int r){ l |= SZ; r |= SZ; vector<int> res; while(l <= r){ if(l & 1) res.push_back(l++); if(~r & 1) res.push_back(r--); l >>= 1; r >>= 1; } return res; } template<typename FlowType, size_t _Sz, FlowType _Inf=1'000'000'007> struct Dinic{ struct Edge{ int v, dual; FlowType c; }; int Level[_Sz], Work[_Sz], N; vector<Edge> G[_Sz]; void clear(){ for(int i=0; i<_Sz; i++) G[i].clear(); } void AddEdge(int s, int e, FlowType x){ G[s].push_back({e, (int)G[e].size(), x}); G[e].push_back({s, (int)G[s].size()-1, 0}); } bool BFS(int S, int T){ memset(Level, 0, sizeof(Level[0]) * N); queue<int> Q; Q.push(S); Level[S] = 1; while(Q.size()){ int v = Q.front(); Q.pop(); for(const auto &i : G[v]){ if(!Level[i.v] && i.c) Q.push(i.v), Level[i.v] = Level[v] + 1; } } return Level[T]; } FlowType DFS(int v, int T, FlowType tot){ if(v == T) return tot; for(int &_i=Work[v]; _i<G[v].size(); _i++){ Edge &i = G[v][_i]; if(Level[i.v] != Level[v] + 1 || !i.c) continue; FlowType fl = DFS(i.v, T, min(tot, i.c)); if(!fl) continue; i.c -= fl; G[i.v][i.dual].c += fl; return fl; } return 0; } FlowType MaxFlow(int _N, int S, int T){ FlowType ret = 0, tmp; N = _N; while(BFS(S, T)){ memset(Work, 0, sizeof(Work[0]) * N); while((tmp = DFS(S, T, _Inf))) ret += tmp; } return ret; } }; int N, C; string S; vector<pair<int,int>> V[3]; Dinic<int, (1<<20)+303030> Flow; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> S; N = S.size(); for(int i=0; i<N; i++) V[S[i]-'A'].emplace_back(i, 0); for(int i=0; i<3; i++) if(i != 1) for(auto &j : V[i]) j.second = C++; while(SZ < V[0].size() + V[2].size()) SZ <<= 1; // 1 ~ 2S-1 : segment tree // 2S ~ 2S+B-1 : B // 0, 2S+B : S, T const int src = 0, snk = 2*SZ + V[1].size(); for(int i=1; i<SZ; i++) Flow.AddEdge(i, i<<1, 1e9), Flow.AddEdge(i, i<<1|1, 1e9); for(int i=0; i<V[0].size()+V[2].size(); i++) Flow.AddEdge(i|SZ, snk, 1); for(int i=0; i<V[1].size(); i++){ Flow.AddEdge(src, 2*SZ+i, 1); auto it1 = upper_bound(V[0].begin(), V[0].end(), V[1][i]); if(it1 != V[0].begin()){ for(const auto &j : GetRange(0, prev(it1)->second)) Flow.AddEdge(2*SZ+i, j, 1e9); } auto it2 = upper_bound(V[2].begin(), V[2].end(), V[1][i]); if(it2 != V[2].end()){ for(const auto &j : GetRange(it2->second, V[2].back().second)) Flow.AddEdge(2*SZ+i, j, 1e9); } } cout << Flow.MaxFlow(snk+1, src, snk); }

2-3. 보급

그래프를 명시적으로 만들고 위상 정렬을 하는 것은 그래프의 간선 개수가 $O(N^2)$이기 때문에, 여기에서 더 발전하는 것은 힘들어 보입니다. 다른 풀이를 생각해야 합니다.

$i \neq j, X_i < X_j, Y_i < Y_j$인 순서쌍 $(i, j)$을 고려해야 합니다. 3개나 되는 조건을 모두 고려하는 것은 복잡하므로, $X$ 기준으로 정렬해서 2개의 조건 $i < j, Y_i < Y_j$만 고려해도 되도록 만듭시다.

$i < j, Y_i < Y_j$인 순서쌍 $(i, j)$에 대해 $V_i < V_j$를 만족해야 하므로, $B_i < V_j \leq B_j, A_i \leq V_i < A_j$라고 생각해도 됩니다.
조건을 만족하는 모든 순서쌍 $(i,j)$에 대해, $A_j \leftarrow \max\lbrace A_j, A_i + 1 \rbrace$, $B_i \leftarrow \min\lbrace B_i, B_j + 1\rbrace$를 수행합시다. $A$를 계산할 때는 $j$ 오름차순으로, $B$를 계산할 때는 $i$ 내림차순으로 계산하면 됩니다. 이 과정은 세그먼트 트리의 인덱스로 $Y$ 좌표를 사용하는 것으로 $O(N \log N)$에 수행할 수 있습니다.

이제 새로 수정한 $A, B$를 이용해 $A_i \leq V_i \leq B_i$를 만족하는 $V_i$를 구하는 일만 남았습니다. 이 작업은 회의실 배정 문제처럼 $B$가 작은 기지부터 배정하면 되고, 우선순위 큐를 이용해 $O(N \log N)$에 할 수 있습니다.

여담으로, 2018 KAIST ACM-ICPC Mock Competition의 B번 문제로 출제된 Dumae 문제와 매우 유사합니다. Dumae 문제는 입력으로 DAG가 직접 주어지기 때문에 더 쉽게 해결할 수 있습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

#include <bits/stdc++.h> using namespace std; struct Point{ int x, y, a, b, i; Point() = default; friend istream& operator >> (istream &in, Point &p){ return in >> p.x >> p.y >> p.a >> p.b; } bool operator > (const Point &p){ return b > p.b; } // comparator for min heap }; struct SegmentTree{ static constexpr int SZ = 1 << 18; int T[SZ << 1]; function<int(int,int)> merge; void init(int id, function<int(int,int)> func){ fill(T, T+SZ*2, id); merge = func; } void update(int x, int v){ x |= SZ; T[x] = merge(T[x], v); while(x >>= 1) T[x] = merge(T[x<<1], T[x<<1|1]); } int query(int l, int r){ l |= SZ; r |= SZ; int ret = T[0]; while(l <= r){ if(l & 1) ret = merge(ret, T[l++]); if(~r & 1) ret = merge(ret, T[r--]); l >>= 1; r >>= 1; } return ret; } } Tmn, Tmx; int N, R[252525]; Point A[252525]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N; for(int i=1; i<=N; i++) cin >> A[i], A[i].i = i; sort(A+1, A+N+1, [](auto u, auto v){ return u.x < v.x; }); Tmn.init(N+1, [](int a, int b) -> int { return min(a, b); }); Tmx.init(0, [](int a, int b) -> int { return max(a, b); }); for(int i=1; i<=N; i++){ A[i].a = max(A[i].a, Tmx.query(1, A[i].y) + 1); Tmx.update(A[i].y, A[i].a); } for(int i=N; i>=1; i--){ A[i].b = min(A[i].b, Tmn.query(A[i].y, N) - 1); Tmn.update(A[i].y, A[i].b); } sort(A+1, A+N+1, [](auto u, auto v){ return u.a < v.a; }); priority_queue<Point, vector<Point>, greater<>> Q; for(int i=1, j=1; i<=N; i++){ while(j <= N && A[j].a <= i) Q.push(A[j++]); if(Q.empty()){ cout << "NO"; return 0; } auto p = Q.top(); Q.pop(); if(p.a <= i && i <= p.b) R[p.i] = i; else{ cout << "NO"; return 0; } } cout << "YES\n"; for(int i=1; i<=N; i++) cout << R[i] << " "; }