[백준] 1912번: 연속합 풀이 및 해설(C++)

문제 이미지

풀이

입력되는 수열들을 arr [n]이라고 하자.

연속된 arr[n]의 합 중 가장 큰 것을 구해야 한다. 

이를 위해 arr[n]을 보고 동적계획법으로 값을 결정하는 수열을 dp [n]이라고 하자.

dp [n]은 arr [n]을 마지막 원소로 하는 최댓값이 되는 수열이다.

 

수열의 당장 다음값이 음수더라도 그 수열을 끊지 않고 이어갔을 때 절댓값이 더 큰 양수들을 얻을 수 있다면 수열을 이어나가야 한다.

 

그렇다면 어떻게 이것을 판단할 수 있을까?

 

일단 새로운 값이 나오면 음수더라도 더하되, 현재까지 dp[n]의 값이 음수라면 그냥 새로운 arr[n]값부터 새로 시작하면 된다.

이미 합이 음수가 되어버린 dp[n]은 더이상 답이 될 수 없다. 그냥 새로운 arr[n]부터 시작하면 된다.

 

dp [n-1]에서 arr [n]을 보았을 때 선택지는 2가지이다.

1. dp[n]=dp[n-1]+arr[n]

arr [n]까지 해서 수열에 더한다.

2. dp [n]=arr [n]

지금까지의 수열을 리셋하고 arr [n]부터 다시 만든다.

 

앞서 dp [n]은 arr [n]을 마지막 원소로 포함하는 수열 합의 최댓값이라고 했다.

최댓값이니 둘의 크기를 비교해 둘 중 큰 것을 더하면 된다.

 

그리고 지금까지의 dp [n] 중 최댓값을 출력하면 된다.

 

 

해답 코드

#include <iostream>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main(){
    fastio;
    int n,maxi=-1000000000;
    cin>>n;
    int arr[n]={0},dp[n]={0};
    cin>>arr[0];
    maxi=arr[0];dp[0]=arr[0];
    for(int i=1; i<n; i++){
        cin>>arr[i];
        dp[i]=max(dp[i-1]+arr[i],arr[i]);
        if(dp[i]>maxi){
            maxi=dp[i];
        }
    }
    cout<<maxi;

}

헤맸던 부분

모든 수열을 더한 수열 합인 S를 이용해 구할 수 있을 줄 알았다.

수열의 n번째 항을 An, 1번째부터 n번째 항까지의 합을 Sn이라고 하자.

 m+1번째 항부터 n번째 항까지의 합 중 최댓값 즉 Sn-Sm의 최댓값을 구해야 한다고 생각했다.

하지만 n>=m이라는 전제조건과 음수가 들어왔을 때 오히려 값이 커지는 점을 생각하지 못해 알고리즘을 바꿨다.

 

PLUS

dp [n]을 만들고 그중 최댓값을 찾는 아이디어는 다른 곳에도 유용하게 쓰일 것이다.