2019 한국정보올림피아드(KOI) 고등부 문제 풀이

고등부 1번. 타일

타일 문제는 복잡한 알고리즘을 요구하지 않아서 풀이로 적을 내용은 길지 않으나, 구현 면에서 까다로운 점이 있는 문제이다. 고등부 1번을 풀지 못하였을 경우 다음과 같은 공부법을 추천한다. 고등부 1번 뿐만 아니라 어떠한 문제를 해결하더라도 이러한 방식으로 접근하는 것이 좋다.

• 1. 먼저 컴퓨터를 일절 사용하지 않고 펜과 종이만을 사용하여 적절한 수도코드(pseudo-code)로 코딩을 완료해 놓은 후,
• 2. 종이에 적힌 내용을 구현하고 정답 결과를 확인한 후, 틀렸을 경우 1번으로 반복
• 3. 맞았을 경우 다른 좋은 구현을 보고 차이점 분석

Subtask 1/2 (45점)

타일을 교체하는 선택지가 없기 때문에, 문제에서 주어진 입력 하에 차량이 도착점으로 움직일 수 있는 지를 판별하면 된다. 이는 시작점에서부터 타일에 표시된 방향을 따라서 차를 움직이고, 도착점에 성공적으로 도달했는지를 판별하는 식으로 가능하다. 가는 도중 길이 끊어지거나 도착지가 아닌 엉뚱한 곳에 도착하면 답이 아니다. 이 알고리즘은 $O(n^2)$ 이다.

Subtask 3/4 (100점)

각 위치에 대해서 5개의 서로 다른 타일 교체가 가능하고, 위치는 총 $n^2$ 개 있으니, 총 $5n^2$ 개의 타일 교체를 시도해 볼 수 있다. 타일을 교체한 후 경로가 있는지는, 서브태스크 1/2의 요령으로 하면 된다. $5n^2$ 번 $O(n^2)$ 연산을 수행하니 총 시간 복잡도 $O(n^4)$ 에 문제가 해결된다.

여담으로, 이 문제는 $O(n^2)$ 시간 복잡도에도 해결 가능하나, 별로 흥미롭거나 알 가치가 있는 풀이는 아니다.

고등부 2번. 괄호 문자열

Subtask 1 (17점)

$N \le 10$ 이기 때문에 펜과 종이만을 사용하여 여러 시행착오로 답을 찾은 후 이를 출력하는 프로그램을 작성하면 된다.

Subtask 2 (48점)

충분히 좋은 답에 대한 보상을 제공하니, Subtask 3을 풀 지식이 없다면 여기서 창의성을 발휘하면 된다. 다양한 전략이 존재한다.

• () 괄호를 $n$ 번 출력하면 0.29점을 받는다.
• 마찬가지로 () 괄호만을 사용하는데, $F(2n) = "(" + F(n) + ")"$, $F(2n+1) = "()" + F(2n)$ 이라는 귀납적 식을 찾을 수 있다. 이는 $4 \log N$ 개의 괄호만을 사용하며, 40점 가량을 받는다.

이 외 백트래킹 등 다양한 전략이 존재한다.

Subtask 3 (100점)

괄호 문자열은 귀납적으로 정의되기 때문에 재귀적인 해결 방법이 유용하다. 이 문제에서는 괄호 문자열에 대한 Dynamic Programming을 사용하여 문제를 해결한다. $DP[i] = $ ($i$ 라는 답을 얻어낼 수 있는 최적의 문자열) 이라고 정의하자. 일반적인 DP와 다르게 최솟값이 문자열로 정의된다는 것이 특이한 점이지만, 큰 차이가 생기지는 않는다.

DP를 정의하면, 이제 문제에서 주어진 재귀적 정의를 그대로 풀어 쓰면 된다. 대략 다음과 같다:

• $i$ 가 2, 3, 5의 배수일 경우, 예를 들어 2의 배수일 경우, "(" + $DP[i / 2]$ + ")" 가 가능한 답의 후보 중 하나이다.
• 모든 $1 \le j \le i - 1$ 에 대해서, $DP[j] + DP[i - j]$ 가 가능한 답의 후보 중 하나이다.

모든 가능한 후보 중 최솟값을 취하면 되는데, 두 문자열을 비교하는 규칙은 문제에 잘 써져 있으니, 이 규칙을 구현하여 최솟값을 취해 주면 된다. 이 방법대로 모든 $1 \le i \le 1000$ 에 대해 미리 전처리를 해 두고, 각 테스트 케이스마다 필요한 문자열을 출력해주면 된다.

위와 같이 구현을 한 후 로컬에서 테스트를 해 보면 시간 안에 잘 나오기 때문에 굳이 시간 복잡도를 증명할 필요는 없다. 하지만 어렵지 않게 상한을 증명할 수 있다. Subtask 2의 $4 \log N$ 길이의 전략이 존재하기 때문에, 답은 항상 $4 \log N$ 이하의 길이를 가지고, 고로 전처리 시간 복잡도는 $O(N^2 \log N)$ 가 되어 문제를 해결하기 충분하다.

여담으로, 이 문제 역시 $N \le 100000$ 이어도 해결 가능하나, 별로 흥미롭거나 알 가치가 있는 풀이는 아니다.

고등부 3번. 검은 돌

Subtask 1 (9점)

모든 정점 부분집합을 순회한 후, 해당 정점 부분집합이 이루는 그래프가

• 트리인지 (즉 연결되어 있는지)
• 돌을 몇 개 가지고 있는지

를 확인한다. 이 정보를 모두 취합하면 모든 $q = (i, j)$ 에 대한 답을 저장하는 2차원 행렬을 구할 수 있고, 모든 쿼리에 대해 출력해주면 된다. 정점 부분 집합의 개수가 $2^N$ 개이니, 시간 복잡도는 $O(2^N \times N + Q)$ 이다.

Subtask 2 (36점)

트리 DP를 사용하여 문제를 해결할 수 있다. (이 글에서는 트리에서 DP를 어떻게 하는지는 따로 소개하지 않겠다.) 우리가 관심있는 내용은 서브트리의 크기와 검은 돌의 개수이니, 이 인자들을 고려하여 다음과 같은 DP 점화식을 세울 수 있다.

$DP[v][i][j] = ($정점 $v$ 를 포함하는 서브트리 내에, $i$ 개의 정점을 가지고 $j$ 개의 정점에 검은 돌이 놓여 있는 서브트리가 존재하는가?)

일반성을 잃지 않고 입력이 이진 트리라고 가정하면 (이것이 왜 일반성을 잃지 않는지 모르겠다면 트리 DP에 대해서 공부하자.) 이 동적 계획법을 각 노드에 대해서 $O(sz(L)^2 \times sz(R)^2)$ 시간에 합쳐줄 수 있다. 결국 $O(N^5)$ 시간 복잡도 알고리즘이 유도되는데, 대부분의 경우에서 상수가 상당히 작다는 것을 알 수 있고, 고로 모든 $N \le 100$ 크기의 트리에서 잘 작동한다. 모든 $DP[v][i][j]$ 값을 알고 있다면 쿼리에 응답하는 것은 간단하다.

사실 본인은 $O(N^5)$ 과 $O(N^3)$ 사이의 복잡도를 가진 쉬운 풀이를 잘 모르기 때문에, 이에 대해 좋은 의견이 있다면 댓글로 적어주면 좋을 것 같다.

Subtask 3 (64점)

입력이 갑자기 커졌기 때문에, 위의 DP 테이블은 이제 잡을 수도 없다. 풀이 방향을 완전히 바꿔서 그리디로 접근하면 잘 풀리지 않으니, 위 DP를 최적화하는 방향으로 문제를 해결한다. 정확히는, 상태 전이를 최적화하는 것도 아니라, 상태의 개수 자체를 최적화하는 식으로 문제를 해결한다. 여기서, 다음과 같은 Lemma가 등장한다.

• Lemma. $DP[v][i][j]$ 가 참인 $i$ 는 연속된 구간을 이룬다. 즉, 어떠한 두 정수 $l, r$ 이 존재하여, $DP[v][l][j], DP[v][l+1][j], \cdots, DP[v][r][j]$ 만이 참이 된다.
• Rough Proof Sketch. 트리 정점 개수에 대한 귀납법을 사용하면 된다. $v$ 의 두 자식 노드 $p, q$ 에 대해 해당 성질이 성립한다면, $DP[p][][x], DP[q][][j - x]$ 를 AND로 묶어준 경우에 대해서도 해당 성질이 성립한다. 이제 $p$ 를 루트로 하고 $x$ 개의 노드를 포함하는 최소 서브트리와 $q$ 를 루트로 하고 $j-x$ 개의 노드를 포함하는 최대 서브트리를 생각해 보자. $p$ 에서 노드를 아무거나 빼면 $x-1$ 개의 노드를 포함하게 되며, $q$ 에서 노드를 아무거나 추가하면 $j-x+1$ 개의 노드를 포함하게 된다. 이는 $DP[p][][x], DP[q][][j - x]$ 를 AND로 묶어준 구간과 $DP[p][][x-1], DP[q][][j - x+1]$ 를 AND로 묶어준 구간이 교집합을 가짐을 뜻한다. 고로 둘의 합집합은 하나의 구간이 되고, 전체에 대해서도 성립한다.

이 점을 활용하면, DP에서 $i$ 라는 인자를 가지고 있을 필요가 없이, $i$ 의 가능한 최솟값과 최댓값을 반환하는 DP를 구현한 후, 나중에 각 $j$ 에 대해서 가능한 $i$ 의 범위를 저장해 놓으면 쿼리를 $O(1)$ 에 응답할 수 있다. DP 정의는 다음과 같이 바뀐다:

$DPmin[v][j] = ($정점 $v$ 를 포함하는 서브트리 내에, $j$ 개의 정점에 검은 돌이 놓여 있는 서브트리의 최소 크기는 무엇인가?)

$DPmax[v][j] = ($정점 $v$ 를 포함하는 서브트리 내에, $j$ 개의 정점에 검은 돌이 놓여 있는 서브트리의 최대 크기는 무엇인가?)

각 노드에 대해 $O(B^2)$ 시간에 합쳐주면 $O(NB^2)$ 시간에 문제가 해결된다.

Subtask 4 (100점)

위 DP를 구현할 때, 두 노드를 합쳐주는 가장 일반적인 방법은, 왼쪽 서브트리에서 $min(B, sz(L))$ 만큼의 크기들을 전부 순회해 보고, 오른쪽 서브트리에서 $min(B, sz(R))$ 만큼의 크기들을 전부 순회하는 것이다. 이를 합치면 각 노드에 대해 $min(B,\ sz(L)) \times min(B, sz(R))$ 만큼의 시간을 소모하게 될 것이다.

이러한 일반적인 방법으로 DP를 구현해 주면 놀랍게도 만점이 나온다. 그 이유는, 위 알고리즘의 시간 복잡도가 $O(NB)$ 이기 때문이다. 아래에 그 이유를 증명한다.

• Lemma. 이진 트리가 주어질 때, 각 노드에 대해서 $min(B,\ sz(L)) \times min(B, sz(R))$ 를 더한 값은 많아야 $O(NB)$ 이다.
• Proof. 더블 카운팅을 사용한다. $min(B, sz(L))$ 은 왼쪽 노드의 서브트리에 있는 수들 중 DFS preorder 번호가 가장 높은 $B$ 개의 정점의 수며, $min(B, sz(R))$ 은 오른쪽 노드에서 DFS preorder 번호가 가장 낮은 $B$ 개의 정점의 수이다. 이러한 두 정점 쌍의 개수는, DFS preorder 상 거리가 $2B$ 인 정점 쌍의 개수보다 작거나 같 다. 이는 $O(NB)$ 이다.

고로, $O(NB)$ 시간에 문제가 해결되고, $B \leq N$ 이니 $O(N^2)$ 에 문제가 해결된다. 여담으로, 똑같은 방식으로 사실 Subtask 2의 풀이가 $O(N^4)$ 라는 것을 증명할 수 있다.

이러한 류의 방법으로 풀리는 문제로는, KOI 지역본선 2006 트리 분할, Coder's High 2016 트리의 변화, BOJ 16216 우산, Codeforces 1097G Vladislav and Great Legend 등이 있다. (연습 문제라고 할 만큼 쉬운 문제들은 아닌 것 같다..)

고등부 4번. 고압선

Subtask 2 (35점)

최적해는 항상 다음 두 형태 중 하나이다:

• 입력으로 주어진 두 점 $p, q$ 에 대해서, $\overline{pq}$ 의 수직이등분선
• 입력으로 주어진 세 점 $p, q, r$ 에 대해서, $r$ 에서 $\overline{pq}$ 에 내린 수선의 수직이등분선

증명은 다음과 같다. 최적해의 길이를 $X$ 라고 하자. 각 점에서 반지름 $X$ 인 원을 그었을 때, 우리는 양 옆에 원을 끼면서 어떠한 원도 닿지 않는 직선을 찾아야 한다. 이 직선의 왼쪽과 오른쪽에는 적어도 하나의 원이 접해 있을 것이다 (그렇지 않다면 답을 늘릴 수 있다). 이 원을 $p, q$ 라 하자. 만약 $p, q$ 가 서로 닿아있는 원이라면 이는 첫번째 형태에 대응된다.

그렇지 않다면, 이 두 원에서 멀어지는 방향으로 직선을 회전하는 것을 시도할 수 있다. 만약 이 회전 시도가 성공한다면, 이는 최적해의 양 옆에 원이 접하지 않게 할 수 있다는 (고로 답을 늘릴 수 있다는) 뜻이므로 가정에 모순이다. 고로 $p, q$ 와 별개로, 회전을 못하게끔 직선에 접해있는 원이 하나 더 있음을 알 수 있다. 이 원을 $r$ 이라고 하면, 이제 이 경우는 두번째 형태에 대응된다.

이제 가능한 직선이 $O(N^3)$ 개이니, 이 후보들을 모두 시도해 보면 $O(N^4)$ 알고리즘이 된다.

Subtask 3 (44점)

증명을 제대로 이해했다면, 두 번째 형태에 대한 약간의 관찰로 시간 복잡도를 줄일 수 있다.

선분 $\overline{pq}$ 와 점 $r$ 을 고르고, $r$ 에서 $\overline{pq}$ 에 평행한 직선을 그었다고 하자. 만약 직선 $\overline{pq}$ 와 이 직선 사이 영역 (개구간과 같이, 해당 직선들은 포함하지 않는 영역을 생각하자) 에 점이 존재한다면, 이 선택은 올바른 선택이 될 수 없고, 그렇지 않을 경우에는 항상 ($\overline{pq}$ 와 $r$ 간의 거리) / 2 만큼의 답을 얻을 수 있다.

고로, 직선 $\overline{pq}$ 에 대해서, $ccw(p, q, r) > 0$ 인 점 중 $\overline{pq}$ 에 가장 가까운 점, $ccw(p, q, r) < 0$ 인 점 중 $\overline{pq}$ 에 가장 가까운 점, 이 두 후보만이 올바른 $r$ 의 후보가 된다. 또한, 이로 만든 직선에서 가장 가까운 점은 항상 $p, q, r$ 이니 단순히 수선의 길이를 2로 나눠주면 답을 찾을 수 있다. 이렇게 하면, 두 번째 케이스를 $\overline{pq}$ 당 $O(N)$ 에 처리할 수 있어서 $O(N^3)$ 알고리즘이 된다.

Subtask 4 (74점)

일단, 위 Subtask 3에서 썼던 아이디어를 그대로 사용하여서 첫 번째 형태도 단순화 할 수 있다. 선분 $\overline{pq}$ 의 수직이등분선에 평행하고, $p, q$ 를 각각 지나는 두 직선을 생각하자. 이 두 직선 사이의 (이번에도, 두 직선을 포함하지 않는) 영역에 점이 존재한다면, 이 선택은 올바른 선택이 아니고, 그렇지 않다면, ($\overline{pq}$ 의 길이) / 2 만큼의 답을 얻을 수 있다. 이렇게 되면 후보를 지정해 주고 직접 거리를 계산해 줄 필요가 없어진다.

이제, 결국 문제는 다음과 같은 질의를 빠르게 처리하는 것이다:

• $\overline{pq}$ 의 수직이등분선에 평행하고, $p, q$ 를 각각 지나는 두 직선 사이의 영역에 직선이 있는가?
• $\overline{pq}$ 에 대해서, $ccw(p, q, r) > 0$ 인 점 중 $\overline{pq}$ 에 가장 가까운 점, $ccw(p, q, r) < 0$ 인 점 중 $\overline{pq}$ 에 가장 가까운 점이 무엇인가?

특정한 방향 벡터 $v$ 를 고정하고, 모든 점을 $v$ 와의 외적 값이 증가하는 순서대로 점을 정렬하자. (정확하게 표현하기 위해 조금 비직관적으로 설명하였다. 직관적이지만 틀린 설명 방식은 다음과 같다: $(-10^{100}, 0)$ 과 점 $v - (10^{100}, 0)$ 를 잇는 직선과의 거리가 증가하는 순으로 정렬했다고 생각할 수도 있고, 모든 점에서 $v$ 방향으로 양 옆에 직선을 그었을 때의 $y$ 절편을 기준으로 정렬했다고 생각할 수도 있다.) 이 때 위 질의는 다음과 같은 식으로 해석될 수 있다:

• $\overline{pq}$ 에 수직한 방향벡터를 기준으로 정렬했을 때, $p, q$ 가 정렬된 배열 상에서 인접한 위치에 있는가?
• $\overline{pq}$ 에 평행한 방향벡터를 기준으로 정렬하면 $p, q$ 는 정렬된 배열 상 인접한 위치에 있게 된다. 이 위치를 $i, i + 1$ 이라 할 때, $i-1, i+2$ 번 위치에 있는 점은 무엇인가?

답을 구해야 하는 방향 벡터가 $O(n^2)$ 개 존재하니 이러한 방식은 문제를 해결하기 좋지 않아 보인다. 하지만, 각도를 기준으로 sweeping을 하는 식으로 위 질의를 오프라인으로 처리할 수 있다. 일반성을 잃지 않고 방향 벡터들이 $x$ 좌표가 증가하는 방향으로 향한다고 하자. 초기 $v$ 가 $(0, -1)$ 방향으로 향한다고 하면, 각 점은 $x$ 좌표가 증가하는 순으로 정렬되어 있을 것이다. 이 과정에서 $v$ 를 점점 시계 반대 방향으로 회전시키면, $v$ 의 방향벡터가 $\overline{pq}$ 와 평행해지는 순간, 두 점 $p, q$ 의 위치가 바뀌게 되고, 이러한 식으로 계속 $v$ 를 $(0, 1)$ 방향으로 돌리다 보면 결국 $x$ 좌표가 감소하는 순으로 정렬되어 있을 것이다. 이 과정의 중간에서, $v$ 의 방향벡터가 $\overline{pq}$ 와 평행해 지는 순간에는, 모든 점들이 방향벡터 $\overline{pq}$ 순으로 정렬되어 있음을 알 수 있다. 고로, 모든 중요한 이벤트 $\overline{pq}$ 를 각도 순으로 정렬한 후, 두 점의 위치를 바꾸는 것을 시뮬레이션하면서 정렬된 배열을 관리하고, 그 와중에 주어진 쿼리를 처리할 수 있다.

이제 문제는 다음과 같이 해결할 수 있다. 모든 점 $p, q$ 에 대해서, $\overline{pq}$ 에 수직하거나 평행한 방향벡터를 모두 모아 각도순으로 정렬한다. 만약 $\overline{pq}$ 에 평행한 방향벡터가 나온다면 두 점을 바꿔주는 식으로 배열을 관리해줄 경우, 각 이벤트를 처리하는 순간 해당 이벤트로 주어진 방향벡터를 기준으로 모든 점들이 정렬되어 있다. 고로 각 질의를 $O(1)$ 시간에 응답해 줄 수 있다. 이러한 방식으로 문제를 해결하면, 각도 정렬에 가장 많은 시간이 소모되므로 $O(N^2 \log N)$ 시간에 문제가 해결된다.

Subtask 5 (100점)

세 점이 한 직선 상에 주어진다고 하면, 단순히 두 직선 사이가 비어있는 지를 판별하는 것이 "배열 상에서 인접한지" 로 판별이 되지 않는다고 생각할 수 있다. 같은 기울기의 점들이 여러개가 있으면, 배열 상에서 인접하지 않아도 두 직선 사이가 비어있을 수 있기 때문이다. 하지만, 그럼에도 불구하고 인접함을 판별하는 것만으로 문제를 해결할 수 있다. 다음과 같은 두 가지 사항만 신경써 주면 된다:

• 같은 방향벡터의 이벤트가 여러 개가 있다면, 이벤트를 모두 처리한 후 해당 선과 평행한 점들이 모두 순서가 뒤집히게끔 이벤트들을 잘 나열한다.
• 각도마다 consistent한 순서를 유지하기 위해서, 같은 기울기의 이벤트가 여러 개 있으면, 스왑 이벤트를 모두 처리한 후 쿼리를 처리한다.

이렇게 될 경우, $p, q$ 가 정렬된 배열 상 인접한 위치에 있지 않더라도, 배열 상 인접한 위치에 있으며 $p, q$ 와 동일한 값을 반환하는 다른 점이 존재한다. 고로, 크게 다르지 않은 코드로 똑같이 문제를 해결할 수 있다. 이를 관찰하지 못했다면, 적당한 이진 탐색을 통해서도 문제를 해결할 수 있으며, 이에 대해서는 설명을 생략한다. 시간 복잡도는 여전히 $O(N^2 \log N)$ 이다.

비슷한 방식으로 해결되는 문제에는 Croatian Team Selection 2009 빨간점 파란점, JOI Open Contest 2017 Bulldozer 가 있다.

여담으로, 이 문제는 Doubly-connected edge list 자료 구조를 사용하여 $O(N^2)$ 시간 복잡도에도 해결할 수 있다. 실제 대회에서 사용할 이유가 있을 만큼 고성능은 아니라고 생각하나, 관심이 있다면 배워 보는 것을 추천한다 (Looking for a Challenge p144 참고).