[ BOJ 백준 13398번 - 연속합 2 ] 해설 및 코드

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

목적

n개의 정수 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하자. (수를 하나 제거할 수 있다.)

 

 

접근법

1. 백준 1912번 - 연속합 문제에서 수 제거 조건만 추가된 문제이다. 점화식을 조금만 수정하면 된다.

 

2. s[i]를 a배열의 i번째 요소를 끝으로 하는 최대 연속합으로 정의하면, s[i]는 a[i] + max(s[i-1], 0) 이다.

 

3. t[i]는 a의 i번째 원소까지의 최대 연속합에서 1개의 원소를 뺀 최대값으로 정의하면, t[i]는 max(s[i-1], t[i-1] + a[i]) 이다. 

 

4. 구해야 하는 값은 s[1]~s[n], t[1]~t[n]중 최대값이다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,s[2][2],num,idx=0,ans;
    cin>>n>>s[idx][0];
    ans=s[idx][0];
    s[idx][1]=-1000;
    while(--n){
        idx^=1;
        cin>>num;
        s[idx][0]=num+max(s[idx^1][0],0);
        s[idx][1]=max(s[idx^1][0],s[idx^1][1]+num);
        ans=max(ans,max(s[idx][0],s[idx][1]));
    }
    cout<<ans;
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.