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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

간단한 예시를 통해서 어떤 경우가 최대가 되는지 구해보자.

[ 5 , 10 , -17 , 8 , 9 ] 라는 배열이 있다고 가정해보자. 그리고 지금부터 "x번째 값을 선택했을 때, 최대가 되는 연속합" 을 구해볼 것이다.

그럼 가장 먼저 첫 번째 값 부터 확인을 해보자.

첫 번째 값 까지 왔을 때 최대가 되는 경우는 값이 얼마일까 ?? 당연히 '5'일 것이다.

다른 선택권이 존재하지 않는 경우이다.

두 번째 값인 '10' 을 확인해보자. 연속합의 최대가 되는 경우는 얼마일까 ?? 최대가 되는 경우를 알아보기 전에, 이 경우에 선택할 수 있는 경우에 대해서 살펴보자.

아마 2가지 Case가 존재할 것이다.

1. 첫 번째 값을 선택하지 않고 , 두 번째 값을 시작점으로 하는 연속합으로 계산하는 Case.

2. 첫 번째 값을 선택하고 , 이어서 연속적으로 두 번째 값 까지 합해서 계산하는 Case.

1번 Case의 경우, 첫 번째 값인 '5'를 선택하지 않고, 두 번째 값인 '10'을 선택하는 경우이기 때문에, 이 경우에는 나올 수 있는 값이 '10' 이 된다.

2번 Case의 경우, 첫 번째 값인 '5'를 선택하고 , 연속적으로 두 번째 값인 '10'을 선택하는 경우이기 때문에, 이 경우에는 나올 수 있는 값이 5 + 10 = '15'가 된다.

당연히 더 큰 값은 2번째 Case에 의한 '15'이니, 이 경우에는 연속합의 최댓값은 '15'가 될 것이다.

세 번째 값인 '-17'을 확인해보자. 연속합의 최대가 되는 경우는 얼마일까 ? 이 경우 또한, 최대가 되는 경우를 알아보기 전에, 발생 가능한 경우를 따져보자.

1. 1번값 ~ 3번값 까지 연속적으로 모두 쭉 더하는 경우.

2. 2번값 ~ 3번값 까지 연속적으로 더하는 경우.

3. 1번, 2번값을 버리고, 3번 값만 계산하는 경우.

위와 같이 3가지 경우가 발생할 것이다.

1번 Case의 경우 , 5 + 10 + (-17) = -2

2번 Case의 경우 , 10 + (-17) = -7

3번 Case의 경우 , -17

그래서 세 번째 값을 선택했을 경우, 연속합이 최대가 되는 경우는 1번 Case인 -2가 될 것이다.

네 번째 값으로 넘어가기 전에 이 부분에서 문제 해결에 관련된 부분 한 가지만 짚고 넘어가보자.

1번 Case의 " 5 + 10 + (-17) " 과 2번 Case의 " 10 + (-17) " 을 다시한번 살펴보자.

여기서 " 5 + 10 + (-17) " & " 10 + (-17) " 빨강색 글씨들에 주목해보자.

위의 2개의 식을 보면 , '-17'은 어차피 공통으로 갖고 있는 값이니 무시한다고 가정하면 , 결과적으로 '5 + 10' 과, '10' 만을 비교하는 과정이 남게 된다. 그런데 ! 이 부분은 이미 우리가 계산을 했던 부분이다.

어디서 ? 바로 위에서 말했던 두 번째 값을 선택했을 때, 구할 수 있는 연속합의 최댓값을 구하는 부분에서 계산을 했던 부분이다. 따라서 , 세 번째 값을 선택했을 때, 연속합을 구하기 위한 경우로 위에서는 3가지를 언급했지만, 그 중에서 사실 위의 2가지 Case는 이미 계산을 했던 과정으로써, 비교를 할 필요가 없다는 것을 의미한다.

그럼 , "5 + 10" 과, "10" 이 무얼 의미하는 값이였는지 다시한번 정리해보자.

5 + 10은, 두 번째 값에서 연속합의 최대값을 구하기 위해서 첫 번째 값부터 두 번째 값까지 모두 더한 연산 결과를 의미하고 ,

10은, 위와 같은 상황에서, 첫 번째 값을 버리고, 두 번째 값만을 선택했을 때의 연산 결과를 의미한다.

즉 ! 위의 2가지 경우에서 우리가 구할 수 있었던 것은, "두 번째 값까지 선택했을 때, 얻을 수 있는 연속합의 최댓값" 이였다.

결과적으로, 세 번째 값을 구하는 과정을 보면, "두 번째 값 까지 선택했을 때, 얻을 수 있는 연속합의 최댓값" 에다가 + "세 번째 값을 선택하는 경우" vs "두 번째 값 까지 선택했을 때, 얻을 수 있는 연속합의 최댓값"을 선택하지 않고, "세 번째 값 만을 선택하는 경우" 이렇게 2가지 경우로만 나눌 수 있다는 것이다.

깔끔하게 다시한번 정리해보면 , "세 번째 값을 선택했을 때, 얻을 수 있는 연속합의 최댓값" 은

1. "두 번째 값까지 선택했을 때, 얻을 수 있는 연속합의 최댓값 + 세 번째 값"

2. "두 번째 값 까지 선택했을 때, 얻을 수 있는 연속합의 최댓값을 버리고 , 세 번째 값 만을 선택"

하는 2가지 경우로 비교할 수 있다는 것이다.

그럼 여기서, 세 번째 라는 글씨 대신에 'N번째' 라는 글씨를 대입시켜서 위의 말을 다시한번 적어보면 다음과 같아진다.

"N번째 값을 선택했을 때, 얻을 수 있는 연속합의 최댓값" 은

1. N - 1번째 값 까지 선택했을 때, 얻을 수 있는 연속합의 최댓값 + N번째 값

2. N - 1번째 값 까지 선택했을 때, 얻을 수 있는 연속합의 최댓값을 버리고 , N번째 값 만을 선택

위의 2가지 Case 중 더 큰 값이 N번째 값을 선택했을 때, 얻을 수 있는 연속합의 최댓값 !

그럼 위의 일반화된 식이 옳게 적용되는지 네 번째, 다섯 번째 값들로 확인을 해보자.

현재 까지 구한 연속합의 최댓값들을 적어보면 [ 5 , 15 , -2 ] 이다.

네번째 값을 선택했을 때 얻을 수 있는 연속합의 최댓값은

1. 세 번째 값 까지 선택했을 때, 얻을 수 있는 연속합의 최댓값 + 네 번째 값

2. 세 번째 값 까지 선택했을 때, 얻을 수 있는 연속합의 최댓값을 버리고 , 네 번째 값 만을 선택

하는 경우 중 더 큰 값이다.

1번 Case는 -2 + 8 = '6' 이 되고 , 2번 Case 는 '8' 이 된다.

즉 ! 네 번째 Case의 경우 연속합의 최댓값은 '8'이 된다.

다섯 번째 값을 선택하는 경우도 마찬가지로 계산해보면...

1. 8 + 9

2. 9

위와 같이 2개의 값을 비교하게 되고 , 연속합의 최댓값은 17이 된다.

즉 ! 각 인덱스들을 선택했을 때 구할 수 있는 연속합의 최댓값은 [ 5 , 10 , -2 , 8 , 17 ] 이 되고, 이 중 최댓값은 17이다.

따라서 위의 예시의 정답은 '17'이 된다.

이를 코드로 표현하기 위해서 본인은 하나의 배열을 사용해 주었다.

DP[] 라는 1차원 int형 배열을 사용해 주었는데 , DP[a] = b 의 의미는 "a번째 값을 선택했을 때, 구할 수 있는 연속합의 최댓값은 b입니다." 를 의미한다.

위의 내용을 토대로 점화식을 적어보면..

DP[N] = Max(DP[N - 1] + Arr[i] , Arr[i]) 가 된다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    DP[1] = Arr[1];
    int Answer = DP[1];
    for (int i = 2; i <= N; i++)
    {
        DP[i] = Max(Arr[i], DP[i - 1] + Arr[i]);
        Answer = Max(Answer, DP[i]);
    }
    for (int i = 1; i <= N; i++) cout << DP[i] << " ";
    cout << endl;
    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;
}