[Algorithm]Baekjoon 13398번 :: 연속합 2

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

13398번: 연속합 2

 
 
int n;
int arr[100001] = { 0 };
int leftSum[100001] = { 0 };
int rightSum[100001] = { 0 };
vector<int> negativeNumIndices;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
        
        if (arr[i] < 0)
        {
            negativeNumIndices.push_back(i);
        }
    }
 
    if (n == 1)
    {
        cout << arr[0];
        return 0;
    }
 
    int sum = arr[0];
    leftSum[0] = sum;
 
    for (int i = 1; i < n; ++i)
    {
        sum = max(sum + arr[i], arr[i]);
        leftSum[i] = sum;
    }
 
    if (negativeNumIndices.size() == 0)
    {
        cout << leftSum[n - 1];
        return 0;
    }
 
    sum = arr[n - 1];
    rightSum[n - 1] = sum;
 
    for (int i = n - 2; i >= 0; --i)
    {
        sum = max(sum + arr[i], arr[i]);
        rightSum[i] = sum;
    }
 
    int answer = -0x3f3f3f3f;
    for (int i = 0; i < negativeNumIndices.size(); ++i)
    {
        int tempSum = 0;
        int index = negativeNumIndices[i];
 
        if (index == 0) // 맨왼쪽꺼면
        {
            tempSum = rightSum[index + 1];
        }
        else if (index + 1 == n) // 맨 오른쪽꺼면
        {
            tempSum = leftSum[index - 1];
        }
        else // 가운데있을 때.
        {
            tempSum = max(leftSum[index - 1] + rightSum[index + 1], max(leftSum[index - 1], rightSum[index + 1]));
        }
 
        answer = max(answer, tempSum);
    }
 
    cout << answer;
}

 

 

최대 연속합을 구하는 문제인데, 딱 한가지의 숫자를 지울 수 있단다..

숫자를 무조건 지우는게 이득이 되려면, 지우려는 숫자가 음수여야만 한다.

0이상인 숫자는 굳이 안지우고 그냥 연속되게 냅둬도된다. 한번밖에 사용할수없는 지우기찬스를 여기다 쓸 필요가 없다는 것이다.

 

그러니 일단 지워야할 후보숫자는 무조건 음수이다.

그렇다면 이런생각을 할 수 있다.

 

'각 음수를 기준으로, 양옆의 최대값을 알 수 있다면 값비교를 통해서 정답을 알 수 있지 않을까?'

 

여기서 양옆의 최대값이란, 아래와 같은걸 의미한다.

 

1 2 -3 4 5 

 

라는 5개의 숫자가 주어졌을 때, -3은 음수이니 기준으로 잡는다.

그리고 양옆의 최대값이란, 먼저 왼쪽의 최대값은 첫번째 숫자부터시작해서 -3숫자인덱스의 바로 왼쪽까지, 즉 숫자2까지의 최대값을 의미한다.

오른쪽의 최대값은 끝숫자부터 시작해서 -3숫자의 바로 오른쪽, 즉 4까지의 최대값을 의미한다.

그러면 -3 왼쪽에서 만들수 있는 연속최대값은 1+2인 3이고, -3의 오른쪽에서 만들 수 있는 연속최대값은 4+5인 9이다.

여기서 기준인 -3을 삭제한다고 치면, 양옆의 숫자들은 연속될 수 있으니 3 + 9 == 12가 된다.

 

위의 과정을 수행하기 위해 먼저 왼쪽,오른쪽에서 시작해서 반대편까지 최대값을 구해놔야 한다.

코드에서의 leftSum은 0번째인덱스부터 n-1번째 인덱스까지의 최대연속값들을 의미한다.

마찬가지로 rightSum은 n-1번째 인덱스부터 0번째 인덱스까지 최대연속값들을 의미한다.

 

그러면 leftSum은 어떻게 구할것인가?

0번째인덱스부터 n-1번째까지 가면서 비교를 통해 값을 업데이트한다.

값은 반드시 연속되어야한다. 그렇기 때문에 각 차례마다 두가지 선택지가 주어지고, 값이 더 큰것을 선택해야 한다.

 

1. 현재차례의 값(arr[i])를 sum에 누적시킬것인가

2. 이때까지 쌓아온것을 버리고 arr[i]부터 다시시작할것인가.

 

두 값중 큰거를 선택하면 된다.

rightSum도 마찬가지로 똑같이 구하면 된다.

 

이렇게 전부 구하고 나면, 음수를 기준으로 잡고 answer에 최대값을 업데이트를 할 것이다.

단, 음수에 해당하는 인덱스가 끝쪽이라면, 즉 인덱스가 0이거나 n-1이라면, 각각 한쪽씩 막혀있기 때문에 반대쪽의 최대값이 해당 음수를 삭제했을때의 최대값이 된다.

 

예를들어 음수가 0번째 인덱스면 rightSum[1]이 최대값이 된다. 마찬가지로 음수가 n-1번재 인덱스면 leftSum[n-2]가 최대값이 된다.

삭제할 음수가 끝쪽이 아닌 가운데에 있으면, 총 3가지의 값들 중 큰값으로 업데이트 해야 한다.

왜? 해당 음수를 삭제했을 때 왼쪽과 오른쪽이 연결되는데, 사실 무조건 연결시킬필요가 없다.

연결시켜서 손해인 경우가 발생할 수 있기 때문이다.

음수기준으로 왼쪽덩어리는 양수인데, 오른쪽덩어리가 음수이면? 오른쪽덩어리를 굳이 합칠필요가 없는것이다.

 

그렇기 때문에 3가지 경우의 수(왼쪽덩어리값,오른쪽덩어리값,왼쪽덩어리값 + 오른쪽덩어리값) 중에서 가장 큰값을 선택해야하는 것이다.