BOJ 2593/15994 엘리베이터

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

문제 링크


내가 만든 엘리베이터 2 (더 강한 문제)



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)\)만에 찾으면 된다.

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