백준 24971 262144 revisited

 

문제 링크: https://www.acmicpc.net/problem/24971

24971번: 262144 Revisited

백준에 문제를 푼 사람이 3명 밖에 없다! usaco 정풀이랑 본질적으로는 같은데 접근 방식이 조금 다른 것 같아서 글을 써본다.

 

usaco 정풀: http://usaco.org/current/data/sol_prob1_platinum_open22.html

 

예전에 262144 문제를 봐서 그런지 처음에는 dp식 접근을 하려고 했다. 하지만 O(N^2)개의 dp 상태를 잡지 않고서는 어떠한 dp를 잡아야 될지 모르겠어서 관찰이나 했다.

 

$N(N+1)/2$개의 경우를 모두 따지기 전에 원래 문제 262144에 대한 다양한 관찰들을 시도했는데, 각 정수마다 리프 노드를 만들어서 두 정수를 합칠 때마다 새로운 노드를 parent로 하는 트리를 만든 뒤에 max(depth+정수)를 구한다던가 $a_l$과 $a_r$ 사이에 두 정수보다 많이 작으면 정수들이 놓여있다면 적당히 큰 수들로 바꿔줄 수 있다는 식으로 생각을 했는데 잘 안 풀렸다.

 

그래서 스위핑 식으로 생각을 하려고 했다.

가장 작은 정수부터 시작해서 점차 합쳐나간다고 생각하자. 가장 작은 정수가 $x$라고 생각하자. $x$와 인접한 정수 $x+k$가 있다고 하자. $k \geq 1$이면 $max(x, x+k)=max(x+1, x+k)$이기 때문에 $x$를 다른 정수와 합쳐서 $x+1$이 되도록 하지 않는다면 $x$를 $x+1$로 바꿔줘도 결과가 똑같다는 것을 알았다.

이로 인해서 $x$ 2개가 연속해서 있으면 $x+1$로 합쳐줘야 된다는 생각도 했고, $x$가 $2k$개 있으면 2개씩 합쳐셔 $x+1$이 $k$개 생기게 된다는 것을 알았다.

따라서 가장 작은 정수부터 생각하면서 합칠 수 있으면 합치고 합칠 수 없으면 1을 키워나가는 방식을 계속 반복하다보면 262144를 풀 수 있다.

 

이제 $N(N+1)/2$개의 경우를 모두 따지는 것에 대해서 생각을 해보자.

각 구간에서 가장 큰 정수가 $y$라고 하면 정수들을 작은 것부터 합쳐서 결국 $y$만 남게 되었을 때 남아있는 $y$의 개수만 중요하다. 그래서 분할정복을 가장 큰 정수를 기준으로 남는 구간들에 대해서 구간의 prefix와 suffix에 대해서 각각 정수들을 합친 뒤 $y$가 몇 개 남는지 세주면 된다. 이를 naive하게 하면 prefix와 suffix의 개수가 $O(N^2)$개가 되어서 안 된다. 따라서 이를 구간의 prefix / suffix에 대해서 $y$가 $k$개 남는 prefix / suffix의 개수를 관리해주면 된다. 분할 정복 과정에서 $y$를 기준으로 남는 구간들을 합친 뒤에 생긴 $y$의 개수가 $m$개 있다면 $y$들을 2개씩 합치고 나서 생기는 $y+1$의 개수는 $m/2$개가 되어서 결국 관리하는 prefix / suffix의 개수는 $O(N)$개로 bound된다. $y$가 $m$개 있으면 최종적으로 생기는 정수는 $y+log_2(m)$ 이하이기 때문에 $O(NlogN)$에 문제를 풀 수 있게 된다.