[BOJ 20968] Group Photo

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

20986번: Group Photo

Tag : dynamic programming, prefix sum

 

문제요약

수열 \(A\)의 인접한 두 원소들을 swap해가면서 \(A_i<A_{i+1}+2\)를 \(1\leq i < N\)에서 만족하도록 만들어야한다.

이 때 최소 swap 횟수를 구하라.

 

풀이

관찰이 조금 필요하다.

\(1\)보다 큰 수 중에서 \(1\)의 왼쪽에는 \(1\)보다 작은 수 또는 \(2\)만이 올 수 있다.

그래서 \(1\)의 앞은 \(\{i,i-1,i-2,...,2,1\}\)또는 \(\{1\}\)과 같은 형태가 된다.

\(1\)부터 \(i\)까지를 reverse시키거나 또는 가만히 놔두거나하는 두가지 경우가 문제의 조건을 만족한다.

\(i+1\)부터는 쉽다. \(i+1\)을 처음의 \(1\)처럼 보면된다.

따라서 문제의 조건을 만족하는 수열은 \(\{1,2,3,4,...,N-1,N\}\)또는 이를 몇몇 구간으로 분할해 0개 이상의 구간을 뒤집은 것이다.

 

여기까지 생각하는 것도 험난하다...

 

\(D_i := 1~i\)를 조건을 만족하도록 잘 정렬시키는 최소 swap 횟수

\(D_i=\min_{1<=j<i}{\{D_j+}\)\(j+1\)부터 \(i\)가 reverse된 형태를 만들기 위해 필요한 최소 swap 횟수 \(\}\)

 

reverse하지 않은 \(\{i+1,i+2,...j-1,j\}\)의 최소 횟수와 비교해 둘 중 최소를 넣어야하는거 아니냐? 라고 할 수 있다.

\(\{1,2,3,4,5\}\)와 같은 경우일 것이다. 원소를 한개 포함하는 구간을 뒤집으면 아무 변화가 없다.

그래서 위의 경우는 \(D_4 + \{\)5를 위치로 가져오는 최소 swap 횟수\(\}\)에서 고려가 될 것이다.

 

첫 관찰을 했다면 위의 점화식까지 도출하는 과정은 어렵지 않다. 

중괄호 안의 \(\{j+1,j+2,...i-1,i\}\) 부분이 굉장히 까다로운데 버블 소트의 최소 스왑 횟수를 모든 \((l,r)\)에 대해 구해야하기 때문이다.

 

독특한 정의의 prefix sum을 만들면 이를 \(O(N^2)\)에 처리할 수 있다.

\(C_{i,j}:=\)인덱스가 i보다 크며 값은 j보다 큰 원소의 개수 (내림차순에서의 inversion)

이것 때문에 prefix sum태그가 달렸다. \(C_{i,j}\)는 \(C_{i+1,j}\)를 통해 \(O(1)\)에 구할 수 있으니

\(O(N^2)\)전처리를 성공해냈다.

 

그럼 이제 아래와 같이 문제를 풀 수 있다.

\(D_i=D_j+(j,N]\)의 inversion 합 - \((j,i]\)에서의 inversion 합

 

시간복잡도 : \(O(N^2)\)

 

썸넬용 사진