BOJ 13398 연속합 2

 

문제 링크 : https://www.acmicpc.net/problem/13398

13398번: 연속합 2

 

dp 문제에서 초기화는 늘 어려운 문제임을 상기시켜 주는 문제.

기본 연속합 문제에 두 가지 추가적으로 고려해야할 사항이 생겼다.

 

1. 적어도 하나의 수를 선택할 것. (모두 음수로 이루어지 수열의 경우를 주의해야 한다.)

2. 하나를 제거하고 연속합을 만들 수 있다.

 

dp[0][i] = i 를 번째 항으로 끝나는 최대 연속합

으로 정의하자. 이 경우

$$ dp[0][i]= \max( dp[0][i-1], 0) +arr[i] $$

를 점화식으로 갖게 되는데 반드시 arr[i]가 더해지므로 1 의 조건(적어도 하나가 선택)을 만족시킨다.

 

문제는 다음에 있다.

dp[1][i] = i 번째 항까지 하나가 제거된 최대 연속합

으로 정의했다. dp[1][0] 는 하나가 제거된 연속합이므로  dp[1][0]=0 으로 두었고

$$ dp[1][i] = \max( dp[1][i-1] +arr[i], dp[0][i-1] ) $$

의 관계식을 만족할 것 같았다.

 

그러나...

이렇게 하면,

길이가 1 인 수열의 경우 dp[1][0]=0 은 선택을 하나도 하지 않은 상황이 되므로 문제가 발생하고,

또한 음수로만 이루어진 경우에 ans=max(ans, blar blar~) 에서 계속 0을 선택하게 된다.

 

물론, 길이가 1 인 수열은 따로 거르고 추가적인 장치로 문제를 해결할 수도 있으나...

아예 dp[1][i] 의 정의를 바꾸자.

dp[1][i] = i 번까지 길이가 1 이상인 하나의 항이 제거된 연속합

이 경우 dp[1][0]은 존재하지 않으나 편의상 arr[0]으로 두면 이 후의 계산에서는 문제없이 적용된다.

 

#include<bits/stdc++.h>

using namespace std;

int arr[100000], dp[2][100000];

int main(){
    int n; scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&arr[i]);
    
    dp[0][0]=dp[1][0]=arr[0];
    int ans=arr[0];
    for(int i=1;i<n;i++){
        dp[0][i]=max(dp[0][i-1],0)+arr[i];
        dp[1][i]=max(dp[1][i-1]+arr[i], dp[0][i-1]);
        ans=max(ans, max(dp[0][i],dp[1][i]));
    }
    
    printf("%d\n",ans);
}

 

다른 사람들은 어떻게 실수 없이 dp 초기화를 척척 해내는지 모르겠다.