[BOJ] 백준 15493 - 수 고르기

난이도 - Diamond IV
태그 - 그리디 알고리즘, 우선순위 큐 (여기서 다루는 풀이와는 다릅니다.)
https://www.acmicpc.net/problem/15493

* 결국은 이 포스트가 Aliens trick 설명이였네요, 이름만 들었던 알고리즘이라 이렇게 배울 줄은 생각을 못 했습니다 😂
처음으로 백준문제 포스팅을 해보네요. 쉬운 거 같다가도 어려운 문제에다가 발상이 신기해서 올려봅니다 😊
Note - 풀고 나서 알게 된 건데 1150번 문제에서 원이라는 조건만 더했네요, 그리디 발상은 여러 블로그에 나와있으니 생략하겠습니다 (솔직히 엄밀한 증명을 못 하겠어요 저 방법은)

Solution - 이분 탐색 + Dynamic Programming

Motivation - 정답이 2³¹보다는 작다고 했으니 혹여나 log(Max ans)번의 이분탐색으로 답을 찾을 수 있지 않을까...? 했습니다
Motivation 2 - K에 제약이 없우면 문제는 전형적인 O(N) DP 문제에 해당합니다*. 결국 단조성만 찾으면 되겠네요!

* N>2이므로 1번째 원소가 없는 경우와 N번째 원소가 없는 경우 두 가지로 나뉘어 원을 선으로 풀어버리면 됩니다.

여기서 특이점은 f(K) 값 (여기서 f란 어떤 길이 N의 순열에서 (원순열 아님) k개의 원소를 조건에 맞게 골랐을 때 최댓값을 의미합니다)에 대한 이분 탐색이 아닌, f(i)-f(i-1)에 대한 이분 탐색을 활용하는 것입니다.

Key Observation 1 -  f(i)-f(i-1)은 단조감소이다.

원소를 더할수록 점점 더 증가량이 적어질 것이라는 것은 들어보면 직감상 맞는 것 같은데 증명이 꽤 까다롭습니다.

Proof)
f(i-1)과 f(i+1)의 값을 만족하는 상태를 A와 B라 합시다.
그러면 이제 A와 B를 'xor'시킬 수 있습니다. 즉, A와 B 둘 중 하나에만 속하는 원소들만 신경을 써주면 됩니다.
이 때, A와 B의 교집합에 속한 원소를 P개라 할 시,
B에만 속한 원소는 i+1-P개로, A에만 속한 원소보다 2개 더 많습니다.
그리고 A하고 B가 연속된 원소인 것은 조건에 모순이므로, B-A-B-A...-B인 chain이 하나 이상 존재해야 합니다. (즉, B n+1개, A n개)
이 때, 이 chain 위에 있는 B하고 A를 모두 뒤바꾸고, 나머지 원소는 모두 그대로인 A'과 B'을 생각합시다.
그러면 A'과 B'의 원소들 역시 이웃하는 짝이 없고, 둘 다 고른 원소의 개수가 i개이므로 둘 다 f(i) 이하여야 합니다.
f(i-1)+f(i+1)=sum(A)+sum(B)=sum(A')+sum(B')<=f(i)+f(i)
정리 시 f(i)-f(i-1)>=f(i+1)-f(i)입니다.

이 때 주의해야 할 점이 모든 원소가 음이 아닌 정수에도 불구하고도, f(i)-f(i-1)는 음수가 될 수 있습니다. 한 번 [5,1000,5]와 같은 케이스를 생각해보자. 이걸 모르고 구현하다가 WA만 몇 번을 맞았습니다... 근데 f(i)에서 원소 하나를 빼면 최대 f(i-1)임을 이용해 커봤자 -2³¹이라 둘 수 있습니다.


결국은 f라는 함수가 위로 볼록하다는 것인데, 아래의 그림을 한 번 봅시다.

기울기가 줄어들수록 이와 접하는 x좌표는 늘어나고 있습니다. f가 위로 볼록하기 때문입니다.
여기서 f(x)=ax+C가 접선이 있다는 것인데, 이게 무슨 뜻이냐면 f(x)-ax의 최댓값을 만들어주는 x의 값 opt(a)는, 단조감소인 것입니다.

Key Observation 2 - K에 제약을 두지 않고 DP를 하면 이분탐색으로 답을 찾을 수 있다.

근데 f(x)는 여기서 x개의 수를 고르는 것이니, 각 수를 고를 때마다 a만큼을 잃는 것과 동치라 볼 수 있습니다. 또는 각 원소에 a를 뺀 채로 구하는 것이라 볼 수 있습니다. 그러면 우리는 a를 [-2³¹, 2³¹-1]에서 이분탐색이 가능합니다.

여기서 주의할 점이 추가로 더 있습니다.

1) f(i)-f(i-1)이 단조감소여도 일정할 수 있는 구간이 있습니다. (Key Observation 1을 자세히 보시면, 등호가 들어가있습니다)
단조성을 유지시키기 위해 opt(a)가 최솟값을 만드는 모든 x 중 최솟값이라 정의하겠습니다.
2) 이분탐색할 때 어떤 점을 찾아야 할까요? -> opt(a)의 일부분이 다음과 같다고 합시다.
[5,4,4,2,2,2,1]
K = 4 -> 4 중 아무런 점이나 잡으면 됩니다.
K = 3 -> 4 이후의 점일 때 최소라 가정하면 1)에서 만든 가정에 모순됩니다. 그리고 모든 f(i)-f(i-1) 값은 정수이기 때문에, 처음으로 나타나는 2에서, i=3일 때 같은 최솟값을 가짐을 장담할 수 있습니다.
이를 종합하면, 처음으로 opt(a)가 K보다 작거나 같은 지점을 이분탐색으로 찾으면 됩니다.
이 지점을 찾았다면, 이 때 최댓값에 K * a를 다시 더해주어, 최종 답을 구하면 됩니다.

참고로 시간제한에 유의해야 합니다. 매번 dp 배열을 재사용할 수 있기에 초기화할 필요가 없습니다 (하면 TLE가 납니다)

Source Code - http://boj.kr/103a9d8d513e4e70888a0b9c37e038db