Educational Codeforces Round 149 (Rated for Div. 2) F. Editorial for Two

Problem - F - Codeforces

F번 치곤 쉽게 나와서 진짜 오랜만에 F번을 풀어봤다.

 

가장 안좋은 방법은 k개를 선택하고 k개를 차례대로 순회하면서 답을 구하는 방법이다.

이 방법은 O(nCk * k) 시간 복잡도 이므로 말도 안되는 시간이 걸린다.( 대략 30만 팩토리얼 )

k개를 선택하는 방법은 괸장히 비효율적이므로 다른 방법을 생각해 내야 한다.

 

답은 문제의 정의를 다르게 하면 된다. 디스크립션에서 k개를 선택하고 분할해서 계산한다. 우리는 분할 먼저 하고 k개를 선택할 것이다. ( 생각해 보면 이 풀이가 떠올리기 어렵지 않은 이유가, 연산의 순서를 바꾸는 방법은 흔한 풀이 방법중에 하나이기 때문일 것이다. ) 분할 먼저 하고 왼쪽에서 d개, 오른쪽에서 k-d개를 선택해서 답을 구해주면 된다. 이 풀이의 시간 복잡도는 O(nnlogn) 이므로 풀이에 적합하지 않은 시간 복잡도 이지만 처음처럼 막무가네인 시간복잡도는 아니다.

 

여기에서 이분탐색을 적용하면 시간복잡도를 줄일 수 있다. 정답이 특정 값 기준으로 가능, 불가능이 나뉘므로 이분탐색을 사용할 수 있다. 정답이 x보다 작거나 같은지 O X 를 결정하는 결정 문제로 바꾸면 된다는 이야기이다. 여기까지가 O(nlogk) 이다. 여기서 왼쪽 구간과 오른쪽 구간을 각 각 정렬하게 되면 nlogn이 붙어서 O(nnlogklogn) 이 되어버린다. 따라서 정렬을 사용할 수 없다. 여기서 시간복잡도를 줄일 수 있는 아이디어가 다이나믹 프로그래밍이다. 이전에 구했던 값을 재사용 하면서 구하면 O(nlognlogk) 만에 답을 구할 수 있다. 만약 분할을 먼저 하고 이분탐색을 시도하게 되면 이분탐색 시 이전에 사용한 값을 재사용 할 방법이 없기 때문에 잘못된 풀이다. 이분탐색을 먼저 하고 분할을 하게 된다면 우선순위 큐를 사용하여 풀이할 수 있다. 배열에서 총 합이 x보다 작거나 같은 원소 수의 합이 최대인 그룹의 원소의 개수를 접두사 배열과 접미사 배열 두 개에서 각 각 nlogn 만에 구할 수 있다. 그룹에 원소를 하나 추가하고 그룹에서 가장 큰 값을 하나씩 빼가면서 그룹이 합이 x보다 작거나 같아질 때 까지 빼면 된다. 원소가 n번 추가될 수 있으므로 우선순위 큐로 관리한다면 O(nlogn) 시간복잡도로 접미사 배열과 접두사 배열을 만들 수 있다. 그리고 나서 구간을 나눠 가면서 가능한지 판단하면 된다. 따라서 시간 복잡도는 O(logk(nlogn + n)) 이므로 결론적으로 O(nlognlogk) 시간복잡도가 도출된다.