[c++] 백준 1912 - 연속합(분할 정복, 동적 계획법)

0. 주어진 문제

연속합 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	44751	12193	8410	26.968%

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1 

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1 

33

1. 풀이

이번 문제는 조금 간단하게 해결할 수 있었다.

1) i번째 숫자가 입력되면, cache[i]에 숫자를 저장한다.

2) cache[i] + cache[i-1] > cache[i]인 경우,

    cache[i] = cache[i] + cache[i-1]

    아닌경우, cache[i]는 이번에 입력된 값을 저장을 하면 된다.

이후, cache배열에 저장되어있는 숫자 중 가장 큰 값을 출력하면 된다.

+)2019.04.25 공부를 하다가 최대합에 관련된 부분이 나와서 코드에 추가해보았다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include <cstdio>   int cache[100002]; int MAX = -1111;   int main() {     int N;     scanf("%d", &N);     for (int i = 1; i <= N; i++){         scanf("%d", &cache[i]);           if (cache[i - 1] + cache[i] > cache[i])             cache[i] += cache[i - 1];           if (cache[i] > MAX)             MAX = cache[i];     }       printf("%d\n", MAX); } Colored by Color Scripter

cs

+) 최대합 관련 다양한 구현

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
 
const int MIN = numeric_limits<int>::min();
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도:O(N^3)
int inefficientMaxSum(const vector<int>&A) {
    int N = A.size(), ret = MIN;
    for (int i = 0; i < N; ++i) 
        for (int j = i; j < N; ++j) {
            //구간 A[i..j]의 합을 구한다.
            int sum = 0;
            for (int k = i; k <= j; ++k)
                sum += A[k];
            ret = max(ret, sum);
        }
    return ret;
}
 
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도:O(N^2)
int betterMaxSum(const vector<int> & A) {
    int N = A.size(), ret = MIN;
    for (int i = 0; i < N; ++i) {
        int sum = 0;
        for (int j = i; j < N; j++) {
            //구간 A[i..j]의 합을 구한다.
            sum += A[j];
            ret = max(ret, sum);
        }
    }
    return ret;
}
 
 
 
//
//4.10 최대연속 부분 구간 합 문제를 푸는 분할 정복 알고리즘
//
 
//A[lo..hi]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도:O(nlgn)
int fastMaxSum(const vector<int>&A, int lo, int hi) {
    //기저 사례 : 구간의 길이가 1일 경우
    if (lo == hi) return A[lo];
    //배열을 A[lo..mid], A[mid+1..hi]의 두 조각으로 나눈다.
    int mid = (lo + hi) / 2;
    //두 부분에 모두 컬쳐 있는 최대 합 구간을 찾는다. 이 구간은
    //A[i..mid]와 A[mid+1..j] 형태를 갖는 구간의 합으로 이루어진다.
    //A[i.mid] 형태를 갖는 최대 구간을 찾는다.
    int left = MIN, right = MIN, sum = 0;
    for (int i = mid; i >= lo; --i) {
        sum += A[i];
        left = max(left, sum);
    }
    //A[mid+1..j] 형태를 갖는 최대 구간을 찾는다.
    sum = 0;
    for (int j = mid+1; j <= hi; ++j) {
        sum += A[j];
        right = max(right, sum);
    }
    //최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾는다.
    int single = max(fastMaxSum(A, lo, mid),
        fastMaxSum(A, mid + 1, hi));
    //두 경우 중 최대치를 반환한다.
    return max(left + right, single);
}
 
 
//
//코드 4.11 최대 연속 부분 구간 합 문제를 푸는 동적 계획법 알고리즘
//
 
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(n)
int fastestMaxSum(const vector<int>& A) {
    int N = A.size(), ret = MIN, psum = 0;
    for (int i = 0; i < N; ++i) {
        psum = max(psum, 0) + A[i];
        ret = max(psum, ret);
    }
    return ret;
}
 
int main() {
    /*int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++){
        scanf("%d", &cache[i]);

        if (cache[i - 1] + cache[i] > cache[i])
            cache[i] += cache[i - 1];

        if (cache[i] > MAX)
            MAX = cache[i];
    }

    printf("%d\n", MAX);*/                //2019.04.25 1차 수정
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,temp;
    vector<int> arr;
    cin >> n;
    while (n--) {
        cin >> temp;
        arr.push_back(temp);
    }
    cout << fastestMaxSum(arr) << endl;
}
//
//맨 뒤에서부터 cache로 만들고
//자기부터 끝까지 더하는데, cache[i]는 자기부터 끝까지 합의 최대크기
//만일 cache[]가 음수를 만나면 stop하도록
//손코딩 부터 해보자.

3. 문제 출처

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

4. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.117~119.