안녕하세요 블로그를 팔까 생각 중인데 마침 재밌는 문제를 최근에 해결해 풀이를 작성해봤어요 피드백 주시면 감사하겟습니당

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

Baekjoon Online Judge

Baekjoon Online Judge

www.acmicpc.net

문제 설명 (의역):

길이가 N인 양의 정수 수열이 있을때 각 최대 K개의 원소가 있는 연속부분수열들로 나눈다. 단, 연속부분수열의 갯수는 최소여야 한다. (수열의 길이가 N일때 부분수열의 갯수는 ceil(N/K)이여야 한다). 각 부분수열의 점수는 그 부분수열의 최솟값으로 정한다. 부분수열들의 점수의 합을 최대로 했을때 그 합을 구하라.

제한:

1 <= K <= N <= 1e6

1 <= 원소 값 <= 1e9

풀이:

우선 문제의 제한이 N<=1e3정도로 낮았다면 어떤 식으로 해결할 수 있을까요? 우선 정확히 ceil(N/K)개의 부분들로 나누고 싶으니, i번째 인덱스까지 나눴고 현재까지 j개의 부분들로 나눴을때 가능한 최대 합 정도로 N^2 DP 모델링이 가능하겠죠.

예제로 DP 테이블 값을 채워 보면

정도로 나옵니다.

여기서부터 바로 최적화를 시킬 여지가 보입니다. 그것도 그럴것이, 우리가 필요한 값은 DP[N][ceil(N/K)]의 값 뿐인데 필요 없는 상태들까지 모두 계산해주고 있기 때문입니다. 하지만 이 최적화를 구체화시키려면 조그만한 관찰이 필요합니다.

어떠한 수열에 대한 최적해를 생각해봅시다.

A[1], A[2], A[3] ... A[N-3], A[N-2], A[N-1], A[N]의 수열에서

C[1], C[2]... C[ceil(N/K)]의 나누는 포인트를 잡아야겠죠.

여기서 임의의 나누는 포인트를 잡습니다. C[i]라고 부르겠습니다. 여기서 한 주장을 하겠습니다.

i의 값은 무조건 ceil(C[i]/K)이고, N-i의 값은 무조건 ceil((N-C[i])/K)입니다.

증명:

우리의 1 순위 목표는 수열을 최소의 갯수의 부분수열로 나누는 것입니다. 점수를 최대화 하는 것은 2 순위적인 목표죠.

i의 값이 ceil(C[i]/K) 보다 크다면, i개를 쓰지 않고도 C[i]까지 분할 할 수 있기에 이는 틀린 답입니다.

i의 값이 ceil(C[i]/K) 보다 작은 상황은 한 부분수열의 원소는 K개로 한정되어 있기 때문에 모순적입니다.

N-I의 값도 비슷한 원리로 증명할 수 있습니다.

이 주장의 정당성을 증명했기에, 우리는 풀이에 결정적인 강력한 사실을 얻었습니다. i번째 인덱스까지 어떠한 수의 부분수열로 나눴을때, 사실 그 부분수열들의 갯수의 후보는 단 하나밖에 없다는 것입니다. 이를 토대로 이번엔 1차원인 DP를 모델링 할 수 있습니다.

이제 마지막으로 구현만 깔끔하게 해주면 마무리 되는데, 이 부분도 쉽지 않습니다. 여기까지 풀이를 도출한 상황에서는 어떤 방식으로 구현하든 풀리긴 하겠지만, O(N) 구현과 O(N log N)의 구현으로 갈리는거 같네요.

우선 제 구현은 O(N log N) 입니다... ㅎㅎ...

구현 설명:

수열을 ceil(N/K)개의 '블럭'으로 나눈다. 첫 번째 블록에 해당되는 인덱스들의 ceil(i/K) 값은 1이고, 두 번째 블록의 인덱스는 2이인 식으로 나눠지기 때문에 각 블럭의 DP 값은 바로 전 블럭의 DP 값으로만 구할 수 있다는 성질을 이용해 구현할 것이다.

임의의 한 블럭을 잡자. 바로 전 블럭의 DP 값은 벌써 구했다고 가정한다. 이 블럭의 i번째 원소의 DP 값을 BLOCK_DP[i] 로 부르겠고 원소의 값은 BLOCK_SEQ[i]로 부르겠다. 전 블록의 j번째 원소의 DP 값을 P_BLOCK_DP[j]로 부르겠고 원소의 값은 P_BLOCK_SEQ[j]로 부르겠다.

여기서, 어차피 우리가 고려해야 하는 구간들은 첫 번째와 두 번째의 블럭 사이에 걸쳐 있으니 BLOCK_SEQ[i]는 max(BLOCK_SEQ[I],BLOCK_SEQ[i-1])로 정의하고 (prefix max) P_BLOCK_SEQ[j]는 max(P_BLOCK_SEQ[j],P_BLOCK_SEQ[j+1])로 정의하겠다 (postfix max).

당연하게도, BLOCK_SEQ 의 값은 i가 증가할수록 증가하고 P_BLOCK_SEQ의 값은 j가 감소할수록 증가한다. 어차피 BLOCK_DP[1...K]의 값은 구해줘야 하니, i를 스위핑하면서 투 포인터로 적당히 BLOCK_SEQ과 P_BLOCK_SEQ의 최댓값을 잘 관리해주면 된다 (우선순위 큐를 이용했지만 단조성을 이용한 O(N)의 구현도 어렵진 않을거 같다).

코드:

핸들을 까기 싫었는데 숨겨도 의미 없을거 같네요.

http://boj.kr/1fa54ee8cfb140deb1a8a2301f1a28e5

Baekjoon Online Judge

Baekjoon Online Judge

boj.kr

끗!!