BOJ 27877 제곱수 덱 2 풀이

 

https://www.acmicpc.net/problem/27877

27877번: 제곱수 덱 2

문제가 상당히 간단하다.

관점을 조금 바꿔보자. 각 카드를 정점으로, 덱을 컴포넌트로 보면, 이 문제는 MST 문제로 환원될 수 있다. 가중치 간선의 곱에 대한 MST인데, 결과에 log를 씌운다 하면, 결국 곱셈이 덧셈으로 바뀌기에, 일반적인 MST 문제와 같다.

 

크루스칼 알고리즘을 생각해보자. 가중치가 적은 간선부터 선택하며 만약 그 가중치를 선택할 때 사이클이 생긴다면 선택하지 않는 식으로 작동하는 알고리즘이다.

 

예제어서 주어진 14에 대한 mst를 한번 만들어보면, 

놀랍게도 가능한 모든 간선을 선택할 때 사이클이 한번도 생기지 않고 mst가 만들어진다. 

또한 N < 14 일때 spanning tree가 만들어지지 않음을 알 수 있다.

 

N = 15일 때는 어떻게 될까? 15와 연결이 가능한 정점들은 1, 10, 21 .. 이 있고, 이 중 10을 선택하는것이 최소이다.

이런식으로 문제를 귀납적으로 풀 수 있다. 이미 만들어진 mst에서, 가장 가중치가 작은 간선을 선택하는 식으로 하면 된다. 이때 만들어질 수 있는 제곱수는 n + n - 1 보다 작거나 같은 제곱수만 가능하기에, 그런 제곱수 중 최소인 것을 선택하면 될 것이다.

 

이런식으로 풀다보면 이미 만들어진 mst에서 추가되는 정점과 다른 방식으로 선택하는 것이 더 좋은 선택지일수도 있지 않을까? 하는 생각이 들 수 있는데, 새로 추가되는 정점과 연결되는 간선이 항상 더 길다. 크루스칼 알고리즘에 의해서 이러한 간선을 선택해주면 안된다. 증명은 모르겠는데 대충 그럴거 같다.

 

식은 정리해보면 새로 추가되는 정점 N에 대하여 $2N - \lfloor\sqrt{2N - 1}\rfloor_{}^{2}$가 나온다.

이제 dp처럼 하면 이 문제를 선형에 해결해 줄 수 있다.

그리고 식에서 중복이 생김을 이용하면, $O(\sqrt{N})$에 풀 수 있다.

 

십덕사전지식이 아닌 다이아를 처음 풀어보는데, 상당히 재밌었다. 문제 자체가 그냥 재밌는듯..