[백준 1912번] 연속합 (C++, Python)

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

1912번: 연속합

이번 포스트에서는 백준 알고리즘 문제인 연속합을 포스팅하도록 하겠습니다.

 

해당 문제는 solved.ac 기준 실버 2에 위치한 문제입니다.

 

먼저 문제입니다.

정수 N이 주어지고, N의 길이의 수열이 주어집니다. 이때, 연속된 몇 개의 수를 선택해서 구할 수 있는 합중 가장 큰 합을 구하는 문제입니다. 수는 한개 이상 선택해야합니다.

 

이 문제도 DP 알고리즘 문제로 바텀업 방식으로 해결합니다.

 

브루트포스 알고리즘으로 for문을 통해서 구할 수 있으나, N이 최대 10만이고, 시간제한이 1초로 주어지기 때문에 O(N^2) 로 해결이 불가능한 문제라서 DP를 통해 해결합니다.

 

해당 문제의 점화식은 DP[i] = max(DP[i - 1] + arr[i], arr[i]) 입니다.

 

수열을 읽어 가면서 그 당시의 최대값을 dp 배열에 저장하는 방식으로, 직전 인덱스에서의 최대값 + 현재 인덱스 값을 구하고, 현재 인덱스 값과 비교합니다.

 

문제에서 주어진 예제 1로 보았을 때,

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

처음 DP[0]에는 10이 들어갑니다. 그리고 DP[1]에는 6이 들어가게 됩니다.

필자는 이 부분에서 10이 더 큰데 왜 6이 들어가는지 이해가 안됐으나, 그 이유로는 그 뒤로 연속된 수를 합했을 때, 결국 10보다 커지게 됩니다. 따라서, 현재 인덱스와 이전 인덱스까지의 최대값 + 현재 인덱스를 비교합니다. 현재 인덱스를 선택하게 되는 경우는, 앞의 수들과 연속해서 선택하지 않고 새로 시작하는게 더 큰 케이스가 됩니다.

 

그렇게해서 구해진 DP 배열을 다시 for문을 돌며 최대값을 찾으면 해당 수열에서 구할 수 있는 최대값을 도출해낼 수 있습니다.

 

아래는 C++ 코드입니다.

 

#include <iostream>
 
using namespace std;
 
int dp[100001] = {0,};
int arr[100001] = {0,};
 
int main() {
    int n;
    cin >> n;
 
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
 
    dp[0] = arr[0];
 
    for(int i = 1; i < n; i++) {
        if(dp[i - 1] + arr[i] > arr[i])
            dp[i] = dp[i - 1] + arr[i];
        else
            dp[i] = arr[i];
    }
 
    int max = dp[0];
 
    for(int i = 1; i < n; i++) {
        if(max < dp[i])
            max = dp[i];
 
    cout << max;
 
    return 0;
}

다음은 Python 코드입니다.

 

dp = [0] * 100001
 
n = int(input())
arr = list(map(int, input().split()))
 
dp[0] = arr[0]
 
for i in range(1, n) :
    if dp[i - 1] + arr[i] > arr[i] :
        dp[i] = dp[i - 1] + arr[i]
    else :
        dp[i] = arr[i]
 
max = dp[0]
 
for i in range(1, n) :
    if max < dp[i] :
        max = dp[i]
 
print(max)

점화식을 구하는데 있어서 이전 최대값과 혼동되는 부분을 제외하면 풀이가 쉬운 문제였습니다.

 

다음 포스트에서 또 다른 백준 알고리즘 문제로 포스팅하겠습니다. 감사합니다.