[C/C++ 백준 1912번] 연속합 (Silver 2)

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

1912번: 연속합

처음 이문제를 보자마자 생각한건 배열을 두번 돌면서 모든 i j 에 대해 i부터 j까지의 합을 구해 Max를 구하는 거였지만,, 딱봐도 시간 초과나 뭐 그런 오류가 뜰게 분명하다.

 

분류가 다이나믹 프로그래밍이니, 쪼개서 생각해보자. 일단 떠오르는 아이디어는 N-1에서 구한 연속합을 이용해 N번째의 연속합을 구하는 것이다.

 

N번째 수가 음수일경우 연속합은 N-1번째와 같다.

N번째 수가 양수일경우 ① N번째 수 ② N-1번째 연속합 ③ N-1번째 연속합에서 N번째 수까지의 모든 합

이 세가지 중 가장 큰 것을 선택하면 될 것 같다. 이제 코딩해보자. 

---

#include <stdio.h>
int FindBest(const int num[], int j, int& BestCombiBegin, const int BestCombi[]){
    if(j==0){
        BestCombiBegin=0;
        return num[0];
        }
    if(j<0)
        return BestCombi[j-1];
    else{
        int sum=0;
        for(int i=BestCombiBegin; i<=j; i++)
            sum += num[i];
        if(sum>=BestCombi[j-1] && sum >= num[j])
            return sum;
        else if(BestCombi[j-1] >= sum && BestCombi[j-1] >= num[j])
            return BestCombi[j-1];
        else{
            BestCombiBegin = j;
            return num[j];
        }
    }
        
}
int main(void){
    int n, BestCombiBegin=-1,N[100001]={};
    int BestCombi[100001]={};
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf(" %d",&N[i]);
    }
    for(int j=0; j<n; j++){
        BestCombi[j]=FindBest(N, j, BestCombiBegin, BestCombi);
    }
    printf("%d",BestCombi[n-1]);
    printf("\n%d",BestCombiBegin);
}

---

틀렸다. 예제 입력 1에서 10 -4 3 1 5 6 -35 12 21 -1 경우 12 21 조합을 인지 할 수 있어야 하는데, 알고리즘상 그게 불가능하다. 한 시간 정도 고민하다가 글 쓰는 공돌이님의 풀이(https://sihyungyou.github.io/baekjoon-1912/)를 보고 30분 정도 더 고민한 끝에 왜 저렇게 하면 풀리는지 이해할 수 있었다.

---

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
    int n, num[100001]={};
    int dp[100001]={};//dp[i]는 i를 반드시 포함하는 연속합을 의미한다. 
    int ans;
    scanf("%d",&n);
    for(int i=0; i<n; i++)    scanf(" %d",&num[i]);
    ans = num[0];
    dp[0] = num[0];
    for(int j=1; j<n; j++){
        dp[j]=max(dp[j-1]+num[j], num[j]);
        ans=max(dp[j], ans);
    }
    printf("%d",ans);
}

 

---

dp[i]를 구하는 과정에서, 새로운 연속합을 만들지 아니면 기존의 것에서 더해갈지 결정하게 된다. 새로운 연속합이 기존의 연속합보다 크든 작든 ans 구하는 과정에서 고려하니 신경 쓸 필요도 없고.

위의 예제 입력 1에서 10 -4 3 1 5 6 -35 12 21 -1 에서도 12를 거칠 때 연속합이 12를 포함하게 되면서 12 21을 고려할 수 있게 된다.

 

과정이 별로 없어 보이는데, 빈틈없이 코드가 굴러가는 게 정말 신기하긴 하다. 열심히 해야겠다.