gshscs

'X'로 표시되어 있는 세 영역을 하나의 영역으로 합치기 위해서 'X'를 추가적으로 칠해야 하는 최소값을 구하는 문제이다.

세 영역밖에 없으므로, 연결하는 경우의 수는 두 가지밖에 없다. 영역을 두개씩 각각 연결하거나(예제), 세 영역의 중간지점에서 세 영역을 동시에 연결하는 경우가 있다. 격자가 최대 50*50=2500개밖에 없으므로, 모든 점들 사이의 경우를 다 따져봐도 2500^2=625만가지이다. 따라서 단순하게 모든 경우를 따져도 시간 안에 답을 구할 수 있다.

여러가지 해법들이 있지만, O(N)의 시간 안에 답을 구할 수 있는 간단한 그리디 알고리즘을 소개하겠다.
최소 실행 수는 a[i]와 a[i-1], a[i+1]의 차이의 합의 절반과 같다는 것에 주목할 필요가 있다. 왜 그런지는 잘 생각해보자.

a[i]-a[i-1]은 i등급부터 straight가 시작되는 수를 나타낸다. a[i]와 a[i+1]의 경우에서도 마찬가지이다. 따라서 최소 실행 수는 abs(a[i+1]-a[i])의 합에서 2로 나눈 값이다.

가장 쉬운 방법은 재귀적으로 모든 경우를 다 살펴보는 것이다. 재귀함수에서는 소의 번호 x만 있으면 된다. 1번 소부터 시작해서 조건을 만족하는지 차례로 살펴보면, 최악의 경우 O(K*3^N)의 시간 안에 답을 구할 수 있다. 하지만 적절히 커팅을 하면 대략 O(3^N)의 시간 안에 답을 구할 수 있을 것이다.

재귀함수를 쓰지 않고 답을 구할 수도 있는데, 3진법의 N자릿수를 생각해본다. 그리고 0부터 3^N-1까지 모든 경우를 반복문으로 확인해도 O(3^N)의 시간 안에 답을 구할 수 있다.

소들의 거리가 K 이하일 때 혼잡하다는 데 주의할 필요가 있다. 거리가 K 이하인 모든 경우를 찾으면 될 것이고, 그러면 O(NK)의 시간이 소요될 것이다. 하지만 Sliding Window를 쓰면 계산량을 크게 줄일 수 있다.

[7 3 4 2] 3 4 
7 [3 4 2 3] 4 -> 최대 혼잡도 3
7 3 [4 2 3 4] -> 최대 혼잡도 4

한 Window 안에서 품종이 같은지 확인하기 위해서 해싱을 쓰면 된다.

문제의 조건에서, 소들이 달리는 시간은 길어봤자 100만(10^6)임을 알 수 있다.  따라서 모든 시간에서 두 소의 위치를 측정하면서 'leadership change'가 몇번 일어나는지만 구하면 된다.