티스토리 뷰
문제 링크 : https://oj.uz/problem/view/JOI13_collecting
순서대로 10점 -> 30점 -> 100점 풀이를 최적화하는 과정을 통해 떠올렸다. 점수 배치도, 접근 과정도 굉장히 재미있는 문제였다.
일단 가장 단순하게 떠올릴 수 있는 해법부터 고려해보자. 사진의 어떤 일부분에 대해서, 그 사진을 4등분해야하는지 아닌지 조건을 우선 파악해야한다. 이건 비교적 간단한데, 해당 사진의 크기가 n*n이라고 했을 때, 위아래 선분이 0개 또는 n개 이면서 좌우 선분이 0개 또는 n개이면 해당 사진은 자르지 않아도 된다. 모든 선분이 다 0개 -> 전체 흰색, 둘 중 하나가 n개 -> 전체 검은색, 둘 다 n개 -> 전체 흰색이기 때문이다.
그러면 이제 여기서 4등분을 해야하는 경우는 재귀적으로 같은 함수를 반복해주는 방식으로 구할 수 있다. 위아래, 좌우 선분의 개수는 세그먼트 트리를 이용하면 조금 빠르게 구할 수 있는데, 여기까지 구현해서 제출할 경우 10점을 얻는다.
이제 이걸 어떻게 하면 최적화할 수 있을까? 위의 로직은 T(n) = 4*T(n/2) + O(logn)이기 때문에 대략 O(4^n)의 속도로 동작한다. 매 q개의 쿼리마다 이러한 연산을 해야하니 대충 O(q* 4^n)으로 돌 것이다. 여기서, 4*T(n/2) 부분을 최적화해보자. 여기서 생각한 접근 방법은 이렇다.
편의상 줄을 좌우로 긋는 경우만 생각해보자(상하로 긋는 경우는 완전 동일한 로직이므로).
만약에, 원래 색종이에서 좌우로 선을 하나 그었다고 생각해보자. 만약에 원래 종이에서 위쪽 절반에 선을 그었다면, 이 선은 종이의 아래쪽 절반에는 어떠한 영향도 끼칠 수 없다(이전에 분할된 것과 완전 동일하다). 반대로, 아래쪽 절반에 선을 그었다면 이 선은 종이의 위쪽 절반에는 어떠한 영향도 끼칠 수 없다.
그러면, 선을 그었을 때 영향을 받아 압축 크기가 바뀌는 부분만 계산해줘도 상관없지 않을까? 매번 전체 넓이를 계산하는 게 아니라, 선분을 추가함으로써 바뀌는 넓에만 계산하고, 이런 경우 위아래 중 절반은 볼 필요가 없으므로 4*T(n/2)가 아니라 2*T(n/2)만 봐도 된다. 이렇게 생각할 경우 넓이 변화는 어떻게 계산할 수 있을까?
선을 그었을 때 종이에 변화가 생기는 경우는 다음과 같이 나눠볼 수 있다.
1. 원래 4등분 안 했는데 4등분 하게 되는 경우
2. 원래 4등분 했는데 4등분 안 하게 되는 경우
3. 원래 4등분이었고 그대로 4등분
1의 경우는 원래는 4등분을 안했으므로 위쪽 절반 혹은 아래쪽 절반은 변화가 없다. 이 변화 없는 부분은 사이즈 1씩 두개가 생기므로 +2가 될 것이고, 선을 그어서 변화가 생긴 부분은 일단 두 개가 생겼으니 +2에 추가적으로 4등분 자른 더 작은 사진에서 생긴 변화량까지 추적해야 한다. 즉, 전체 넓이에 4를 더해주고, 변화가 생긴 절반에서의 변화량을 동일한 방식으로 재귀적으로 추가한다.
2의 경우는 반대이기 때문에 -4를 해주고, 동일한 방식으로 재귀적으로 변화를 계산한다.
3의 경우는 현재 시점에서는 변화가 없으므로, 더 작은 사진 범위에서 생긴 변화만 계산해준다.
이렇게 계산해주면 시간 복잡도가 T(N) = 2*T(N/2) + O(logN) = O(2^n)이 된다. 매 쿼리마다 이 계산을 해줘야 하므로 총 시간복잡도는 O(q*2^n). 이 방법으로 20점을 추가 획득할 수 있다(30점짜리).
마지막으로 여기서 더 최적화를 해보자. 이번엔 T(N) = 2*T(N/2) + O(logN)을 T(N) = T(N/2) + O(logN)으로 줄여볼 것이다.
아까전에 좌우에서 절반만 확인했는데, 위 아래는 여전히 둘 다 확인해봐야하기 때문에 여기서 시간이 오래 걸린다. 이 시간을 줄여보자. 위 아래에서 확인에서 우리가 관심 있는 정보는, 사이즈 n짜리 사진들 중에 전체 n이 다 칠해져 있거나 전체 n이 다 칠해져 있지 않거나한 사진들의 개수이다. 왜냐하면, 앞서 말한 4등분 조건 <위아래 선분이 0개 또는 n개 이면서 좌우 선분이 0개 또는 n개>를 기준으로 생각했을 때, 좌우 선분에 수정이 가해졌을 때 위아래 선분이 0개 또는 n개인 사진들만 압축 크기 변화가 영향을 받기 때문이다.
따라서, 이러한 구간의 개수만 빠르게 구할 수 있다면 위 아래도 다 탐색을 할 필요가 없다. 단순히 구한 구간 개수 * 4를 더해주거나 빼주면 되기 때문이다. 이러한 계산은 생각보다 쉽게 할 수 있는데, logN개의 세그먼트 트리를 만들어서 각각의 세그먼트 트리들이 2^N 사이즈의 색종이들에 대해 해당 사이즈 구간이 0개 혹은 n개 칠해진 개수를 관리하게 만들어주면 된다. 그러면 세그먼트 트리 쿼리 한 번으로 개수를 전부 구할 수 있으므로, 이 구한 개수 * 4를 더하거나 빼주면 된다. 이 트리의 업데이트 역시 전체 넓이 변화를 계산하는 과정에서 같이 해줄 수 있다.
따라서, 전체 시간복잡도 O(qn^2) 으로 답을 구할 수 있다.
(세 답을 잘 비교해보면 어디 어디를 수정했는지 알 수 있다)