[ 백준 13398 ] 연속합2 (C++)

백준의 연속합2(13393) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

연속된 수 몇 개를 선택해서 구할 수 있는 합 중 가장 큰 합을 구해야 하는 문제이다.

그 과정에서, 수는 단 한 개 이상 반드시 선택해야 하며, 수열에서 수 하나를 제거할 수 있다.

그럼 우리는 다음과 같이 2가지 나눠서 연속합을 구해볼 수 있다.

1. 숫자를 제거하지 않고 연속합의 최대합을 구하는 경우

2. 숫자 하나를 제거하고 연속합의 최대합을 구하는 경우

각각의 방법들에 대해서 구체적으로 이야기해 보자.

#1. 숫자를 제거하지 않고 연속합의 최대합을 구하는 경우

숫자를 제거하지 않고 연속합을 구할 때, 그 최대합을 구하기 위해서는 어떤 경우를 비교해봐야 하는지 알아보자.

다음과 같은 수열이 있다고 가정해보자. [ 1 , 2 , -10 , 4 , 5 ]

그리고 왼쪽에서부터 하나씩 값을 선택해가면서, 연속합의 최대합을 구해보자.

* 첫 번째 원소 '1'

가장 첫번째 '1'은 비교를 할 수 없기 때문에 무조건적으로 선택되어 질 것이다.

[ 현재까지의 연속합의 최대합 = 1 ]

* 두 번째 원소 '2'

두 번째 '2'를 선택해보자. 두 번째값인 '2'를 선택할 때, 2가지 선택권이 우리에게 주어진다.

1. 기존의 연속합 + '2'

2. 기존의 연속합을 버리고 '2'부터 새로운 연속합의 시작

1번 같은 경우에는 기존의 연속합은 '1'이므로 1 + 2 = '3' 이라는 연속합을 구할 수 있고

2번 같은 경우에는 기존의 연속합을 버리고 '2부터 새로운 연속합을 시작하게 되므로 '2' 라는 연속합을 구할 수 있다.

그러므로 이 중 더 큰 연속합인 1번 경우를 선택해서 '3'이라는 연속합을 구할 수 있다.

[ 현재까지의 연속합의 최대합 = 3 ]

* 세 번째 원소 '-10'

두 번째 원소와 마찬가지로 2가지 선택권 중 더 큰 값을 선택하면 된다.

기존의 연속합을 포함해서 연속합을 계산하면 기존의 연속합 '3' + (-10) = -7 이 되고,

기존의 연속합을 버리고 '-10'부터 새로운 연속합을 시작하면 -10 이 되므로 더 큰 연속합은 -7이 된다.

[ 현재까지의 연속합의 최대합 = -7 ]

우리는 아직 "숫자를 제거하지 않는 경우" 에 대해서 계산을 하고 있으므로 이 과정에서 -10을 없애버릴 수는 없다.

* 네 번째 원소 '4'

마찬가지로 계산해보자.

-7 + 4 = -3 or '4'

위와 같이 -3 혹은 4 두 개의 연속합이 나오게 되는데, 이 떄 더 큰 값은 '4'가 된다.

[ 현재까지의 연속합의 최대합 = 4 ]

* 마지막 원소 '5'

마찬가지로 계산해보면, '9'라는 연속합을 구할 수 있다.

즉 ! 결과적으로 본다면 "숫자를 제거하지 않는 경우" 우리는 연속합의 최대값은 '9'라는 것을 알 수 있다.

이런식으로 우리는 "숫자를 제거하지 않고 연속합을 구했을 때 연속합의 최댓값" 을 구할 수가 있다.

이를 코드로 표현해보자.

Left_Sum[1] = Arr[1];
Answer = Left_Sum[1];
for(int i = 2; i <= N; i++)    
{ 
    Left_Sum[i] = Max(Arr[i], Left_Sum[i - 1] + Arr[i]);
    Answer = Max(Answer, Left_Sum[i]);
}

코드로 표현하면 위와 같이 표현할 수 있다.

위에서 사용된 변수들 부터 간단하게 이야기해보면, Left_Sum[] 이라는 배열은 다음과 같은 의미를 가진다.

Left_Sum[A] = B : A번 원소까지 연속합의 최댓값은 B입니다.

즉, 우리가 위에서 했듯이, A번 원소까지의 연속합의 최댓값을 구하기 위해서는 A - 1번째 원소까지의 연속합의 최댓값 + A번째 원소를 했을때의 값 혹은 이전까지의 연속합을 버리고 A원소부터 새로운 연속합을 시작하는 경우 중 더 큰 값을 선택해주면 된다.

따라서 line5)와 같이 비교를 해주고 있다. i번째 원소부터 새로운 연속합을 시작하는 경우와 i - 1번째 원소까지의 연속합의 최댓값에 i번째 원소의 값을 더해주는 경우 이 2가지를 비교해서 더 큰 값을 저장해 주고 있음을 확인할 수 있다.

그리고 line6)에서 'Answer'라는 변수에 최종적으로 연속합의 최댓값을 저장해주고 있다.

#2. 숫자를 제거하는 경우

그렇다면, 지금부터는 숫자를 제거하는 경우에 대해서 알아보자.

먼저, 숫자를 제거했을 때, 연속합을 구하기 위해서는 어떤 값들을 미리 알고 있어야 하는지 간단하게 그림을 통해서 알아보자.

.

배열이 위와 같이 주어졌다고 가정해보자.

위의 경우에서의 정답은 '21'이다. 가장 가운데 있는 '-500' 원소를 제거하고 연속합을 구하게 되면, 1 + 2 + 3 + ... + 6 으로

21이라는 답을 구할 수 있다.

그렇다면, -500을 제거해야 한다면 어떤 부분에 대한 연속합을 알고 있어야 할까 ?

.

바로 위의 그림과 같이 파랑색 동그라미로 표시되어 있는 부분들(A , B)에 대한 연속합을 알고 있어야 한다.

그런데 우리는 이미 #1에서 숫자를 제거하지 않았을 때의 연속합에 대해서 구해놓았다.

Left_Sum[] 이라는 배열을 이용해서 이 값을 저장해 놓았다.

즉 ! A부분을 Left_Sum[] 으로 표현해본다면, Left_Sum[3] 이 될 것이다.

왜냐하면, Left_Sum[3] 이 가지는 의미는 "3번째 원소까지 연속합의 최댓값" 이기 때문이다.

그렇다면, B부분은 어떻게 표현할 수 있을까 ??

Left_Sum[7] 로 표현이 가능할까 ?? 그렇지 않다. 물론, 위의 경우는 너무 극단적이다 보니 Left_Sum[7]로 계산을 하더라도 정답이 나올 것이다. 하지만 그렇지 않을 경우도 있을 것이다.

.

배열이 이런식으로 주어졌다고 가정을 해보자. 물론, 위의 경우는 모두 양수이기 때문에 숫자를 제거하지 않고 연속합을 구했을 때의 연속합이 최댓값이고 그 값이 정답이 될 것이다. 하지만, 만약 위의 경우에서 가장 가운데 있는 '4'를 제거해본다고 가정해보자. 과연 Left_Sum[3] + Left_Sum[7] 로 계산을 한다면, A부분과 B부분에 대한 합을 구할 수 있을까 ??

아마 제대로 구해지지 않을 것이다.

보다 구체적으로 이야기 해보자면, A부분을 표시하고 있는 Left_Sum[3] 에는 문제가 없지만, B부분을 표시하고 있는 Left_Sum[7] 은 올바른 표현이 아닐 것이다. 왜냐하면, Left_Sum[7]에는 1 + 2 + 3 + 4 + 4 + 5 + 6 의 값이 저장되어 있을 것이기 때문이다. 따라서 'B'부분을 정확하게 표현하고 있는 것이 아니다.

그래서 우리는 이 B부분을 위해서 역순으로 연속합을 구했을 때의 최댓값 또한 알고 있어야 한다.

이 역순으로 계산한 값을 Right_Sum[] 이라고 표현해보자.

즉, Right_Sum[7]에는 '6', Right_Sum[6] 에는 '6 + 5 = 11' , Right_Sum[5] = '6 + 5 + 4 = 15'

이런식으로 값이 저장될 것이다.

따라서 #1의 과정과 똑같은 방식으로 역순으로 계산했을 때 연속합의 최댓값을 구해줘야 한다.

그리고 이를 바탕으로 이제 주어진 배열에서 K번째 원소를 제거하고 난 후의 연속합을 구해보자.

K번째 원소를 제거한다면, K번째 원소를 기준으로 A부분, B부분으로 나뉘게 될 것인데,

A부분은 Left_Sum[K - 1], B부분은 Right_Sum[K + 1]로 표현이 가능할 것이다.

이런식으로 모든 원소를 하나씩 제거해보면서 모든 경우를 비교 및 정답을 갱신해 주면 된다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, Answer;
int Arr[MAX];
int Left_Sum[MAX];
int Right_Sum[MAX];
 
int Max(int A, int B) { return A > B ? A : B; }
    
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    if (N == 1)
    {
        cout << Arr[1] << endl;
        return;
    }
 
    Left_Sum[1] = Arr[1];
    Answer = Left_Sum[1];
    for(int i = 2; i <= N; i++)    
    { 
        Left_Sum[i] = Max(Arr[i], Left_Sum[i - 1] + Arr[i]);
        Answer = Max(Answer, Left_Sum[i]);
    }
    Right_Sum[N] = Arr[N];
    for (int i = N - 1; i >= 1; i--)
    {
        Right_Sum[i] = Max(Arr[i], Right_Sum[i + 1] + Arr[i]);
    }
    
    for (int i = 2; i <= N - 1; i++) Answer = Max(Answer, Left_Sum[i - 1] + Right_Sum[i + 1]);
    
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}