KOI에 등장하는 DP 문제들 #2

2020.09.29 

 

1. 부동산 투자

codeup.kr/problem.php?id=3724

 

정수 수열에서 연속된 1부분 또는 2부분을 골라 합을 최대화하는 문제.

수열 길이 N <= 3e5이다.

 

초기 접근)

최대연속부분합 문제를 해결하는 방법은 다음과 같다.

sum을 들고다니면서 수열의 원소를 차례대로 살펴본다.

sum이 음수이면 새로 갱신하고, sum이 양수이면 수열 값을 더해 들고 간다.

그때 그때 sum의 최대값을 저장하여 답을 구할 수 있다.

 

이 문제를 sum의 최대값과 겹치지 않는 2번째 최대값을  더하는 방향을 해결하려 했다. 물론 2번째 최대값이 음수인 경우 최대값 구간만 선택한다.

 

그런데 합최대구간 X의 합과 어떤 구간 Y의 합을 더했을 때 최대인 것을 보장할 수 있을까?

합이 최대인 두 구간 A1,A2가 존재한다고 가정하자.

A1,A2 중 적어도 하나는 X와 겹친다.둘 다 X와 겹치지 않는다고 하면 A1을 X와 교환했을 때 합이 더 커지기 때문이다.

일반성을 잃지 않고 A1이랑 X랑 겹친다고 하자. A1에서 A1과 X의 겹치는 구간을 제외해 보자. 차구간의 합은 양수이다. 

A1를 잘랐을 때 합이 더 커지면 가정에 모순이기 때문이다. 그런데 X랑 그 차구간을 합치면 X의 합이 더 커진다. 이는 X가 최대구간이라는 것에 모순이다. 고로 합이 최대인 두 구간 중 하나는 합최대구간이다. 

 

겹침을 해결하기 위해 최대연속부분합의 구간을 저장할 필요가 있겠다.

위 방법의 DP 표현은 다음과 같다.

dt[N] : N번째 수를 마지막으로 하는 구간을 고를 때, 구간합의 최대

dt[N] = max(dt[N-1],0) + arr[N] 

Left[N] : dt[N] 구간의 왼쪽 끝

if dt[N-1]>0 : Left[N] = dt[N-1]

else : Left[N] = N

 

dtR[N] : N번째 수를 시작으로 하는 구간을 고를 때, 구간합의 최대

dt[N]과 똑같이 구한다.

mdt[N]을 dt[1]~dt[N] 중 max로 정의하자. mdtR도 마찬가지.

dt[N] 중 최대를 구한 후 모든 합최대구간 중 max( mdt[left[N]-1] , mdtR[N+1] , 0)을 구해 2번째 합최대 구간을 구한다.

 

구현!

 

놀랍게도 반례가 있었다. 합최대구간을 고르지 않는게 최대일 수도 있다. 

위 증명에서 A1,A2중 적어도 하나는 X와 겹친다고 했는데, A1,A2 모두 X와 겹칠 경우 위 증명이 통하지 않는다. ㅋㅋ

 

둘다 겹치는 경우 최대는 어떻게 구할까. 합최대구간을 어떤 한 점으로 분할 한 후 양쪽으로 연속합의 최대값을 구하면 된다. 흠.

이럴겨면 그냥 모든 분할점에 대해 살펴보면 되지 않을까? 

처음 풀이는 틀렸지만 다행히도 구현을 일부만 수정하여 답을 낼 수 있었다.

 

2. 헬기로 짐 운송하기

codeup.kr/problem.php?id=4020

 

어디선가 본 듯한 문제다. 그렇다. DP 연습 1에서 풀었던 <자동차 경주대회>에서 역추적을 제거한 버전이다.

단, 경유지의 수를 최소로 해야 하므로 부등호에 유의하자.

 

 

3. 올림픽 중계 방송

codeup.kr/problem.php?id=4025

 

LDS 1분컷 (longest decreasing sequence)

감소하는 수열에서의 이분탐색을 직접 구현해도 되지만 

수열의 각 원소에 -1을 곱하거나 수열을 뒤집어 LIS를 구하는 것이 편하다.

다음은 LDS의 길이를 초간단하게 구하는 코드이다. 

//https://codeup.kr/problem.php?id=4025
#include<stdio.h>
#include<algorithm>
int main(){
	int k,dt[1010],idx,t=0;
	for(scanf("%*d");~scanf("%d",&k);t+=(idx==t+1))
		k=-k,dt[idx=std::lower_bound(dt+1,dt+t+1,k)-dt]=k;
	printf("%d",t);
} 

k=-k 이 부분만 빼주면 LIS의 길이를 구하는 코드로 변한다.