백준 14458 소가 길을 건너간 이유 10

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

14458번: 소가 길을 건너간 이유 10

초기 상태의 가로지르는 쌍은, inversion counting이므로 nlogn에 처리할 수 있다.

세그트리나 BIT, 또는 병합 정렬로 구현할 수 있다. 

 

그러면 초기 상태가 아닌, k개를 옮긴 상황은 어떻게 생각해야 할까?

 

아이디어만 설명할 것이기 때문에, 편의상 왼쪽의 목초지는 1...N이라고 두자.

또, 마지막 n-k개를 옮기는 상황이나 처음의 k개를 옮기는 상황이나 같은데, 이제 맨 앞의 목초지를 맨 뒤로 보내는 걸 반복하며 가로지르는 쌍의 개수를 업데이트하면 된다고 생각해 볼 수 있다. 

그림에서는, 1을 맨 뒤로 보냈을 때, 3,4,5와의 가로지르는 쌍은 사라지고, 2와 가로지르는 쌍이 새로 생긴다. 즉, 1이 오른쪽에서 4번째이므로, 1보다 앞에 오는 3개와의 쌍이 사라지고, 1보다 뒤에 오는 1개와 쌍이 생겼음을 쉽게 관찰할 수 있다.

1을 포함하지 않는 쌍에는 당연히 영향을 주지 않는다. 

왼쪽에서 맨 앞에 올 경우 오른쪽에서 자기보다 앞인 숫자 Index-1개와 항상 Inversion을 형성하고, 왼쪽에서 맨 뒤에 올 경우 오른쪽에서 자기보다 뒤인 숫자 N-index개와 항상 Inversion을 형성한다는 점을 활용하는 것이다.

즉, 각각의 업데이트에서 Index-1개의 Inversion이 해체되고, N-index개의 Inversion이 생긴다. 

Index는 잘 저장하면 O(1)에 접근이 가능하기에, O(1)에 inversion의 수를 업데이트할 수 있다. 한 바퀴 돌면서 왼쪽과 오른쪽에 대해 수행해 보면 O(n)에 가능한 상황을 전부 확인할 수 있다.

한번 더 적용하면 4개의 Inversion이 해체되어 최소가 된다. 이는 문제에서 주어진 TC와도 같은 형태이다. 

 

PS. 왼쪽과 오른쪽 중 하나만 하면 안된다는 걸 직관적으로는 알겠는데, 반례 찾기가 귀찮다. 알면 제보 부탁드린다.