[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\le 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:=1i$를 조건을 만족하도록 잘 정렬시키는 최소 swap 횟수

$D_i=\underset{1<=j<i}{min}\{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)$

 

썸넬용 사진