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

중등부 1번. 신기한 수

Subtask 2 (100점)

숫자 $N$ 이 주어지면, 해당 수의 일의 자리에 적힌 수는 $N \mod 10$ 이 된다. 이후 숫자를 10으로 나눠주면, 십의 자리, 백의 자리… 에 있던 수들이 모두 일의 자리, 십의 자리로 움직인다. 고로, 이를 반복하면 $O(\log N)$ (입력에서는 최대 8번) 의 단순 연산으로 $N$의 자릿수 합을 알 수 있다. 어떠한 수 $A$ 가 어떠한 수 $B$ 로 나누어 떨어지는 것은, $A$ 를 $B$ 로 나눈 나머지가 0이라는 뜻이니, C++ 나머지 연산자를 사용하여 판별할 수 있다.

중등부 2번. 개구리 점프

Subtask 1 (19점)

어떠한 두 선분 $p, q$ 사이를 오갈 수 있다는 것은, 특정한 좌표 $x$ 가 존재해서, $p, q$ 의 $x$좌표 구간이 모두 $x$를 포함하고, $x$를 포함하며 $y$좌표가 $p, q$ 사이에 있는 다른 구간이 없다는 것을 뜻한다. 모든 $p, q$와 $[-1000, 1000]$ 구간에 있는 $x$를 다 시도해 보면 $2000 \times N^2$ 시간에 모든 쌍에 대해서 해당 정보를 구할 수 있다. 이제 오갈 수 있는 연결 관계를 그래프로 생각하면, 각 쿼리마다 적당한 그래프 탐색 알고리즘 (혹은 Floyd-Warshall) 로 문제를 해결할 수 있다.

Subtask 3 (100점)

사실, 어떠한 두 선분 $p, q$ 사이를 오갈 수 있다는 것은 두 선분의 $x$좌표 구간이 교집합을 가진다는 것과 동치이다. 즉, $y$ 좌표를 깡그리 무시해 줘도 상관이 없다. 이유는, 그 사이에 다른 구간들이 존재한다면, 그 구간들을 그냥 거쳐서 가도 상관이 없기 때문이다 (…)

두 구간 사이를 오갈 수 있는지는 아래 방법으로 판별 가능하다. 모든 구간을 시작점 순으로 정렬하여 순서대로 처리하고, Union-find 자료 구조를 사용하자. 정렬된 배열 상에서 인접한 두 구간이 교집합을 가진다면, Union-find에서 두 구간을 합쳐주고, 두 구간을 합집합으로 대체한다. 이를 시작점 순서대로 반복하면, Union-find 에 각 컴포넌트에 대한 연결 정보가 전부 저장되어 있으니, 두 점이 연결되어 있는지는 모두 빠른 시간에 판별할 수 있다. 시간 복잡도는 $O((N + Q) \log N)$ 이다.

중등부 3번. 드론

Subtask 3/4 (24점)

색에 따라서 드론의 위치가 유일하게 정해지기 때문에, 주어진 $T$ 개의 색은 드론이 방문해야 하는 $T$ 개의 좌표 위치에 정확히 대응한다. 고로, 시작점 -> 1번 위치 -> 2번 위치 -> … -> $T$ 번 위치 -> 도착점 순으로 순서대로 각 셀을 방문하는 최단 시간을 찾는 문제가 된다.

Subtask 3에서는 벽이 없기 때문에, 두 위치의 $X$ 좌표 차와 $Y$ 좌표 차의 합이 두 위치의 거리와 동일하다 (Manhattan Distance), 입력을 순서대로 받으면서 이 정보를 처리하면 된다. 시간 복잡도는 $O(N^2 + M + T)$ 이다.

Subtask 4에서는 벽이 있기 때문에, 두 위치의 거리를 계산하는 것이 위처럼 간단하지 않다. 이 때는 그래프를 도입해서 문제를 해결할 수 있다. 각 격자점을 정점, 인접한 격자점 사이를 오가는 것을 간선이라고 생각하면, 두 위치를 가장 빠르게 오가는 길은 그래프에서 두 정점의 최단 경로에 대응되니, 모든 인접한 쌍에 대한 최단경로를 더하는 식으로 문제의 답을 구할 수 있다. 그래프 입력이 귀찮게 주어지긴 하지만, 어쨌든 적당히 잘 처리하면 일반적인 adjacency list 형태로 저장해 줄 수 있다.

이를 단순하게 하면 $O(TN^2)$ 라서 시간 초과가 날 수 있으나, 우리가 계산해야 하는 최단 경로의 서로 다른 시작점은 많아야 $M+2$ 개이고, BFS 알고리즘은 고정된 시작점에 대해서 모든 도착점까지의 거리를 계산할 수 있다. 고로 $O(M)$ 번만의 BFS로 충분하다. 구현의 편의를 위해서 시작점과 도착점에 $N^2+1, N^2+2$ 이라는 색을 칠해주면 좋다. 시간 복잡도는 $O(MN^2 + T)$ 가 된다.

만점 풀이 (100점)

Subtask 4와의 차이는, 색이 고정된다고 위치가 고정되는 것이 아니라는 점이다. 하나의 색에 대해서도 여러 가지 위치가 있을 수 있고, 이 위치를 어떻게 하는 지에 따라서 거리가 달라진다. 고로 동적 계획법과 같은 방법으로 모든 위치를 시도해야 한다.

$DP[i][j]$ 를, $i$번 LED 타일을 $j$ 번 위치에 드론을 넣어서 밝혔을 때의 최소 시간으로 정의하자. 상태 전이는, $i-1$ 번 LED 타일을 채우기 위해서 드론을 넣은 위치 $k$ 를 모두 순회하면 가능하다. 두 위치에 대한 거리는, Subtask 3/4에서 했던 대로 $O(M)$ 번의 BFS를 통해서 전처리하면 $O(1)$ 시간에 계산할 수 있다.

고로, 한 항을 채우기 위해서 $O(M)$ 시간이 필요하고, 최종적으로 DP를 $O(TM^2)$ 시간에 계산해 줄 수 있다. 여전히 BFS가 필요하기 때문에, 시간 복잡도는 $O(MN^2 + TM^2)$ 가 된다.

중등부 4번. 물 채우기

Subtask 1 (7점)

왼쪽과 오른쪽이 모두 바닥에 닿아 있을 경우 답은 $(M - 2) \times $ (둘 중 작은 쪽 높이), 아닐 경우 답은 0이다.

Subtask 2 (25점)

가장 높은 덩어리를 기준으로 왼쪽에서는 물이 왼쪽으로 흐르고, 오른쪽에서는 물이 오른쪽으로 흐른다. 고로, 각 위치에 고인 물의 높이는 왼쪽에 있는 가장 높은 덩어리 (혹은 그 반대) 의 높이에 따라 좌우된다. 초기에 가장 높은 덩어리를 $O(M)$ 시간에 찾은 후, 덩어리를 기준으로 왼쪽 / 오른쪽으로 훑으면서 각 위치의 물의 높이를 계산해 주면 $O(M)$ 시간에 문제가 해결된다.

Subtask 4 (100점)

문제의 제약 조건 때문에 공중에 떠 있는 덩어리들은 바닥에 닿아 있는 덩어리와 완전히 독립적인 것이라고 생각할 수 있다. 고로 이를 최대한 따로 생각한다.

두 공중 덩어리가 인접한 열에 있고 교집합을 가지면, 두 덩어리가 "연결되어 있다" 라고 생각할 수 있다. 이렇게 연결된 공중 덩어리 컴포넌트들을 계산한다. 이러한 공중 덩어리 컴포넌트들은 위에서 물이 쌓이는 것을 방해할 수 있는 요인이 전혀 없기 때문에, Subtask 2와 같은 요령으로 공중 덩어리 컴포넌트에 고인 물의 양을 $O(M)$ 시간에 계산해 줄 수 있다.

이제, 바닥에 고인 물의 양을 계산해보자. 먼저, 공중 덩어리 컴포넌트가 없다고 생각하고 Subtask 2의 요령으로 물의 양을 계산해 줄 수 있다. 한편, 실제로는 공중 덩어리 컴포넌트 때문에 생각한 위치에 물이 고이지 않았을 수도 있어서, 예상과 다르게 고이지 않은 양이 얼마인지를 알아줘야 한다.

공중 덩어리 컴포넌트에 물이 쌓여 있지만, 어차피 이 물의 양은 앞에서 계산했고, 위에 쌓인 물이 빠지는 일도 없으니, 이 고인 물들을 그대로 덩어리라고 생각하고, 공중 덩어리 컴포넌트에 물이 전혀 쌓이지 않았다고 (그리고 쌓일 수도 없다고) 가정해 줄 수 있다. 이렇게 될 경우 공중 덩어리 컴포넌트는 단순히 물의 공간을 차지하는 장애물일 뿐이므로, 물이 있을 수 있는 위치에 공중 덩어리 컴포넌트가 어느 정도의 위치를 차지하고 있는지만 알면 된다. 이는 (물이 고인 구간 길이) - (물이 고인 구간과, 공중 덩어리 컴포넌트의 교집합 길이) 이니, 단순 계산으로 알아낼 수 있다. 시간 복잡도는 $O(M)$ 이다.