BOJ 2593/15994 엘리베이터

BOJ 2593/15994 엘리베이터

2018. 8. 18. 16:13ㆍ알고리즘 문풀/BOJ 연습

This section is intentionally left blank.

이런 문제는 왜 중등부 지역본선에 나오는 걸까? 그 당시 중학생들은 뭐하는 사람이었던 거지 ㄷㄷ

1. Naive

$O(M^2 N)$

두 엘리베이터가 이어져 있다면 cost 1의 간선을 연결해주고 BFS를 돌리면 된다.

엘리베이터 $i$, $j$의 연결을 판별하기 위해 1층부터 $N$층까지 돌면서 이 층이 두 엘리베이터가 공유하는 층인지 단순 나머지 연산으로 확인해주면 다음의 복잡도를 얻는다.

안타깝게도 이 방식으로는 TLE를 피할 수 없다.

2. Clever

$O(MN)$

imeimi2000의 풀이 방식이다.

그래프의 정점을 에지로 보지 않고 $N$개의 층으로 두자. 정확히는 (현재 층, 현재 엘리베이터)의 총 $O(MN)$개의 노드를 관리한다.

한 엘리베이터로 갈 수 있는 층들 사이는 비용 0의 간선으로 연결하고, 엘리베이터를 갈아타야 하는 경우는 비용 1의 간선으로 연결한 뒤 0/1 BFS를 돌리면 된다.

나는 멍청해서 이건 생각 못했다.

3. Tamreggi

$O(M^2 \sqrt{N})$

Naive를 조금 개조한 풀이이다.

결국 두 엘리베이터가 연결되어 있다는 것은 다음의 정수 방정식의 해가 존재하는 것과 동치이다.

$$ Y_i a + X_i = Y_j b + X_j , \quad a \ge 0, b \ge 0, \quad Y_i a + X_i, \ Y_j b + X_j \le N $$

일반성을 잃지 않고 $Y_i \ge Y_j$라고 하자.

이 때 $a \ge K_{ij} := \left\lceil \frac{X_j - X_i}{Y_i} \right\rceil$가 성립함을 알 수 있다.

그리고 부정방정식의 성질에 의해, 해가 존재한다면 반드시 $a \in [K_{ij}, K_{ij} + Y_j]$인 해 또한 존재하게 된다. 따라서 길이 $Y_j$의 구간만 탐색하면 되는데...아직 $O(N)$이다.

이 때 $Y_i a + X_i \le N$이므로, $a \le \left\lceil \frac{N}{Y_i} \right\rceil$이다! 따라서 $Y_i a + X_i > N$인 경우를 커팅하면 $O(\frac{N}{Y_i})$만에 풀 수 있다.

이 때 $\min (Y_j, \frac{N}{Y_i}) \le \min (Y_i, \frac{N}{Y_i}) \le \sqrt{N}$이므로 두 엘리베이터의 연결 여부를 $O(\sqrt{N})$시간 만에 판별할 수 있다!

그 뒤는 Naive와 같이. 4ms AC가 나온다.

4. Uwek

$O(M^2 \lg N)$??

똑같이 부정방정식을 풀되, 확장 유클리드 알고리즘을 이용하여 특수해를 $O(\lg N)$만에 찾으면 된다.

구현할 자신은 없으니 패스.

레프네 약방