[BOJ-1912][C++] 연속합

문제

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

 

예제 입력 2

10
2 1 -4 3 4 -4 6 5 -5 1

 

예제 출력 2

14

 

예제 입력 3 

5
-1 -2 -3 -4 -5

예제 출력 3

-1

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제 출처

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

1912번: 연속합

 

---

 

문제 해결 방법

• DP를 이용하여 연속합을 구하는 문제이다.
• 문제를 푸는데 시간이 오래 걸렸다.

 

점화식 구하기

• 이 문제를 해결하기 위해 필요한 점화식은 다음과 같다.

$$SUM[i] = Max(SUM[i-1] + num[i], num[i])$$

• $SUM[i - 1]$ 은 0부터 $i - 1$ 까지의 구간합, $num[i]$ 는 $i$ 번째 값을 의미한다.

 

방법 

방법 1

• 구간합(@dp[N - 1] + seq[N]@)과 다음 번째의 값 중 최댓값을 @dp@ 테이블에 채워나간다. (@dp[N] = dp[N - 1] + seq[N]@)
  • 구간합(@dp[N - 1] + seq[N]@)이 다음 번째의 값(@seq[N]@)보다 작다는 것은 @dp[N - 1]@ 이 음수라는 것을 의미한다.
  • 구간합(@dp[N - 1] + seq[N]@)이 다음 번째의 값(@seq[N]@)보다 크다는 것은 @dp[N - 1]@ 이 양수라는 것을 의미한다.
  • 따라서 @dp[N - 1]@ 의 값이 음수일 경우, @dp[N]@ 에는 @seq[N]@이, 그렇지 않을 경우(양수일 경우) @dp[N]@ 에는 @dp[N - 1] + seq[N]@ 이 들어가게 된다. 

int Calc(int n) {
    dp[0] = seq[0];
    result = seq[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(dp[i - 1] + seq[i], seq[i]);
        result = max(result, dp[i]);
    }
    return result;
}

 

방법 2

• 구간합을 업데이트하면서(@dp[N] = dp[N - 1] + seq[N]@) @dp[N - 1]@ 의 값이 양수이면, 연속합을 증가시켜 나가고(@dp[N] = dp[N - 1] + seq[N]@) 그렇지 않으면(음수이면), 연속합 업데이트를 중지시킨다. (@dp[N] = seq[N]@) 
• 결국에는 @방법 1@과 동작 원리가 같음을 알 수 있다.

int Calc(int n) {
    dp[0] = seq[0];
    for (int i = 1; i < n; i++) {
        if (dp[i - 1] > 0) {    // 이전에 구해 놓았던 연속합이 양수이면
            dp[i] = dp[i - 1] + seq[i];    // 업데이트를 하여 연속합을 증가시켜 나간다.
        }
        else {     // 이전에 구해 놓았던 연속합이 음수이면
            dp[i] = seq[i];     // 연속합 업데이트를 중지시킨다.
        }
    }

    // 최댓값 구하기
    result = dp[0];
    for (auto i : dp) {    
        if (result < i) {
            result = i;
        }
    }

    return result;
}

 

예제를 이용하여 확인해보기

• 위의 @방법 1@과 @방법 2@ 모두 비슷한 방식으로 동작한다.
• @pSum@ 은 부분합(연속합), @dp@는 DP 테이블을 의미한다.

 

입력 예제 1

배열 \ N	0	1	2	3	4	5	6	7	8	9
seq	10	-4	3	1	5	6	-35	12	21	-1
pSum	10	6	9	10	15	21	-14	-2	19	18
dp	10	6	9	10	15	21	-14	12	33	32

• @seq@에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합은 33(12 + 21)이다.
• @pSum[0] = seq[0]@이고, $N \ge 1$ 에서 @pSum[N] = pSum[N - 1] + seq[N]@ 이며, @N = 9@ 까지 이 과정을 반복하면 0번째부터 N번째까지의 부분합(@pSum@)을 구할 수 있다.
• @dp[0] = seq[0]@이고, $N \ge 1$ 에서 $dp[N] = max(dp[N - 1] + seq[N], \; seq[N])$ 이며, @n = 9@ 까지 이 과정을 반복하여 @dp@ 테이블을 채운다.
• @dp@ 테이블에서 최댓값(@33@)을 출력한다. 

 

입력 예제 2

배열 \ N	0	1	2	3	4	5	6	7	8	9
seq	2	1	-4	3	4	-4	6	5	-5	1
pSum	2	3	-1	2	6	2	8	13	8	9
dp	2	3	-1	3	7	3	9	14	9	10

• @seq@에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합은 14(3 + 4 + (-4) + 6 + 5)이다.
• @dp@ 테이블에서 최댓값(@14@)을 출력한다. 

 

입력 예제 3

배열 \ N	0	1	2	3	4
seq	-1	-2	-3	-4	-5
pSum	-1	-3	-6	-10	-15
dp	-1	-2	-3	-4	-5

• @dp@ 테이블에서 최댓값(@-1@)을 출력한다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

int n, num, result;
vector<int> seq, dp; 

void Input() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num;
        seq.push_back(num);
    }
    dp.resize(n);
}

int Calc(int n) {
    dp[0] = seq[0];
    for (int i = 1; i < n; i++) {
        if (dp[i - 1] > 0) {    // 이전에 구해 놓았던 연속합이 양수이면
            dp[i] = dp[i - 1] + seq[i];    // 업데이트를 하여 연속합을 증가시켜 나간다.
        }
        else {     // 이전에 구해 놓았던 연속합이 음수이면
            dp[i] = seq[i];     // 연속합 업데이트를 중지시킨다.
        }
    }

    // 최댓값 구하기
    result = dp[0];
    for (auto i : dp) {    
        if (result < i) {
            result = i;
        }
    }

    return result;
}

void Output() {
    cout << Calc(n) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Output();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [동적 계획법 1]
• 실버II

 

연속합(Maximum Subarray)

점화식

$$\text{SUM}[i] = \text{Max}(\text{SUM}[i-1] + \text{num}[i], \; \text{num}[i])$$

• $\text{SUM}[i - 1]$ 은 0부터 $i - 1$ 까지의 구간합, $\text{num}[i]$ 는 $i$ 번째 값을 의미한다.

 

코드

• DP를 이용하여 연속합을 구하는 코드는 다음과 같다.

int MaxSubAry(int n) {
    dp[0] = seq[0];
    result = seq[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(dp[i - 1] + seq[i], seq[i]);
        result = max(result, dp[i]);
    }
    return result;
}

 

참고 사이트

• https://shorturl.at/ezJQ3

Maximum Subarray, using DP