RUN@KAIST 7/23 방학 연습 풀이

1. Fenced In (Platinum)

독특한 형태의 그래프에서 최소 스패닝 트리를 구하는 문제이다. 일반적으로 최소 스패닝 트리는 크루스칼 알고리즘을 사용해서 해결하지만, 여기서 그러한 해결 방법을 택하면, 간선의 개수가 너무 커서 시간 제한을 초과하기 때문에, 더 좋은 아이디어가 필요하다.

아이디어는 크루스칼 알고리즘과 동일하다. 최소 비용으로 합쳐줄 수 있다면 합쳐주는 식이다. 다만 이 때, 하나 하나 일일이 합쳐준다기 보다는 한꺼번에 한 행 / 열을 합쳐준다는 점을 주목할 필요가 있다. 같은 행 (내지는 열) 에서 좌우로 인접한 셀들을 합치는 비용은 모두 똑같기 때문에 한 번에 생각할 수 있기 때문이다. 한 행과 한 열을 한번에 처리해 주면, O(n+m) 개의 이벤트만이 존재하기 때문에 정렬 한번에 쉽게 해결할 수 있을 것이자. 이제 몇 개의 셀이 합쳐지는 지를 계산해야 하는데, 이건 직접 해보면서 계산해보자.

일반성을 잃지 않고 처음에 합치는 것이 한 행이라고 생각해 보자. 그 행을 합치면서 m개의 셀을 합치게 될 것이다. 다음에 또 행을 합쳐야 한다면, m개의 셀... 이렇게 m개의 셀들을 합치게 될 것이다. 이 때 한 열을 합쳐야 하는 상황이 들어왔다고 하면, 모든 셀들을 허물어야 하기 때문에 n개의 셀을 합치게 될 것이다.

이제 한 개 이상의 행과 한 개 이상의 열이 합쳐져 있고, 상황은 그 전과 상당히 달라진다. 행을 합치게 되면, 있던 행 / 열 A / 새로 생긴 행 / 열 B 가 사이클을 이룰 수 있다. 고로 사이클이 생기는 지점에서는 벽을 허물지 않아야 한다. 허물지 않게 되는 벽은 현재 이미 존재하는 열의 개수에 따라서 결정된다. 열을 합치게 되어도 일반성을 잃지 않고 똑같은 상황이다. 이렇게 두 가지 경우에 대해서 처리해 주면 몇 개의 셀이 합쳐지는 지 계산할 수 있다. 이제 답은 쉽게 찾을 수 있다. 

2. Distance

출제할 때는 몰랐는데 풀이로 정리해 보니까 되게 괜찮은 문제.

문제에서 주어진 거리를 계산하는 방법을 먼저 생각해 보자. 결국 dist(A, B) 라는 것은, A에서 몇 개의 소수를 나누고, 그 후 곱해야 B가 되는지를 계산하는 것인데, A와 B를 소인수 분해 한다면, 어떠한 소인수를 빼고 (=나누고) 더해야 (=곱해야) B가 되는지 쉽게 볼 수 있다. 예를 들어 12, 18이라고 하면, 한 쪽은 2 * 2 * 3, 한 쪽은 2 * 3 * 3이니 공통된 2 * 3은 냅두고, 2를 지우고 3을 더하면 12를 18로 만들 수 있다. 공통된 (=냅두는) 수는 정확히 gcd(A, B) 라는 것도 알 수 있다.

이제 거리를 어렵지 않게 구할 수 있다. A의 소인수의 개수 (서로 다른 소인수의 개수 말고, 예를 들어 2^3이면 답은 3)를 p[A] 라고 하면, dist(A, B) = p[A] + p[B] - 2 * p[gcd(A, B)] 라는 식이 나온다. (어째 트리의 LCA를 연상시키는 식이다.) 우리는 dist(ai, aj) 를 최소화하는 서로 다른 i, j를 찾아야 한다. 즉, p[a_i] + p[a_j] - 2 * p[gcd(a_i, a_j)] 가 최소화 되어야 한다. 에라토스테네스의 체를 사용하면 p[]를 1부터 10^6까지 다 O(MaxA)에 채울 수 있다. 먼저 해 놓고 시작하자.

G = gcd(a_i, a_j) 가 고정되었을 때의 dist(A, B)의 최솟값을 찾아보자. 2 * p[G] 가 고정이니, G의 배수인 서로 다른 a_i, a_j 중 p[a_i], p[a_j] 를 최소화하는 두 쌍을 찾아야 한다. 한편, gcd(a_i, a_j) 가 정확히 G일 필요는 없고 G의 배수여도 아무 상관이 없다. 왜냐하면 여기서 최소라고 찾았던 쌍의 gcd가 틀렸다면 (G의 배수라면), 그 G의 배수를 돌 때 어차피 더 작은 값으로 업데이트 될 것이기 때문에 (2 * p[G]가 증가한다!) 결과가 틀려질 일이 없기 때문이다.

그렇다면, p[a_i], p[a_j]는 그냥 G의 배수이면서 다르기만 하면 상관이 없으니, 그냥 G의 배수들을 일일히 돌면서 첫번째 / 두번째 최솟값을 찾아 주면 G가 고정되었을 때의 dist(A, B)의 최솟값을 O(MaxA / G)에 찾을 수 있다. G = 1 -> N까지 이를 반복하니 시간 복잡도는 O(MaxA lg MaxA + N).

3. 서로 다른 소수의 합

1120 이하의 모든 소수들을 아무 알고리즘이나 써서 찾으면 약 200개 정도다. 이 소수들을 사용해서 knapsack 유형의 동적 계획법으로 해결한다. 서로 다른 소수를 뽑아야 하는 것은, 작은 소수부터 큰 소수까지 증가하는 순서대로 소수를 뽑게 하면 된다. 사실 그냥 여러모로 간단한 문제이니 DP 점화식만 적는다. 

 * DP[number, last_prime, sum] : 현재 number개의 소수를 가져왔고, 마지막으로 쓴 소수가 last_prime 번째 이하이며, 그 소수들의 합이 정확히 sum

저기서 이제 last_prime번째 소수를 집어갈지 안 집어갈지로 상태 전이를 구현하면 된다. 테이블이 대충 3M개 정도고 전부 O(1)에 채울 수 있으니 여유롭게 통과한다.

4. 전구를 켜라

회로의 양 끝에 전기가 통하게 하도록 적당히 판을 돌리는 문제이다. 판의 양 끝에 전기가 통한다는 것은 경로가 있다는 것이니, 최소의 판을 돌려서 경로를 만들어 줘야 한다. 

판을 "돌리는" 횟수를 최소화한다고 하니까 당황스러운데, 한번 그래프 이론으로 생각해 보자. 각각의 모서리를 정점으로 두고 전선을 에지라 하면, 판을 돌리는 것은 한 에지를 지워주고 다른 에지를 만들어 줬다고 생각해 줄 수 있다. 

여전히 에지를 지운다는 점이 미심쩍을 수 있는데, 실제로는 에지를 지워줄 필요가 없다. 두 에지를 동시에 사용하는 상황이 없기 때문이다. 위쪽 왼쪽 끝 점을 (0, 0) 이라고 하면, 각 에지가 잇는 두 정점은 i + j 홀짝성이 같다는 것을 알 수 있다. 고로 어떠한 경로를 타던간에 정점의 i + j 홀짝성이 변할 수 없고, 판을 돌리면서 만드는 두 개의 서로 다른 에지는 i + j 홀짝성이 다르기 때문에 두 에지를 동시에 사용하는 상황은 있을 수 없다. 그러면, 에지를 지워줄 필요가 없으니, 판을 돌리는 것은 "새로운 다른 에지를 만드는 것" 이라고 생각해 주자. 

새로운 에지의 개수를 최소로 하는 경로를 찾는 것은 쉽다. 원래 있던 에지를 가중치 0, 새로운 에지를 가중치 1로 주고 다익스트라 알고리즘을 사용하면 되기 때문이다. 경로가 없으면 NO SOLUTION을 찍으면 된다. (사실, (N + M)이 홀수면 무조건 NO SOLUTION이고 아니면 무조건 답이 있다.)

여담으로, 가중치가 0 / 1로만 이루어진 그래프에서는 BFS를 응용해서 선형 시간에 최단 경로를 찾을 수도 있다. 큐 대신 데큐를 사용해 주자. 연결된 정점의 가중치가 1이면 데큐의 뒷쪽 끝에 넣고, 0이면 데큐의 앞쪽 끝에 넣자. 중복된 정점을 두번 이상 처리 안하게 잘 처리하면 BFS를 약간만 바꿔도 문제를 해결할 수 있다.