백준 1912 연속합 C++ 풀이 및 코드

백준 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

문제해설

이 문제는 주어진 수열에서 연속된 숫자들의 합 중 최대값을 구하는 것입니다.
단순히 숫자 몇 개를 골라 합치는 것이 아니라, 반드시 연속된 숫자만 선택해야 한다는 점이 중요합니다.
예를 들어 10, -4, 3, 1, 5, 6, -35, 12, 21, -1이라는 수열에서 답은 12+21=33입니다.
중간에 -35가 있어서 앞에 이어오던 합이 크게 줄어들기 때문에, 그 직후 12부터 다시 시작하는 것이 더 큰 값을 만듭니다.
즉, 연속합이 줄어드는 구간에서는 새롭게 시작하는 것이 더 유리한 경우가 있습니다.

• ✅ 12+21=33처럼 연속된 두 수를 선택하는 것이 가능하고, 최대값입니다.
• ❌ 10과 21을 따로 선택하는 것은 불가능합니다. 연속하지 않기 때문입니다.
• ✅ 2+1+(-4)+3+4+(-4)+6+5=14 역시 최대값이 됩니다. 연속된 구간 안에서 최댓값을 찾아야 합니다.

아이디어

1. 현재 위치에서 연속을 유지할지 새로 시작할지를 선택해야 합니다.

연속합 문제는 연속된 숫자들의 합을 구하는 문제입니다.
따라서 현재 위치에서는 반드시 이전까지의 연속합에 현재 값을 더해 이어갈지, 아니면 지금 위치부터 새롭게 시작할지를 판단해야 합니다.

arr 배열

i	0	1	2	3	4	5	6	7	8	9
값	2	1	-4	3	4	-4	6	5	-5	1

dp 배열

i	0	1	2	3	4	5	6	7	8	9
값	2

첫 번째 값은 선택의 여지가 없으므로 그대로 선택합니다. dp[0] = arr[0] = 2입니다.

2. 이 선택의 기준은 “연속을 유지하는 것이 더 유리한가”입니다.

두 번째 위치 i=1에서 두 가지 선택지를 비교합니다.

• 연속 유지: dp[0] + arr[1] = 2 + 1 = 3
• 새로 시작: arr[1] = 1

연속을 유지하는 것이 3 > 1로 더 유리하므로 연속을 유지합니다.

dp 배열

i	0	1	2	3	4	5	6	7	8	9
값	2	3

3. 연속을 유지하는 것이 불리하다면 새로 시작해야 합니다.

세 번째 위치 i=2에서 두 가지 선택지를 비교합니다.

• 연속 유지: dp[1] + arr[2] = 3 + (-4) = -1
• 새로 시작: arr[2] = -4

연속을 유지하는 것이 -1 > -4로 더 유리하므로 연속을 유지합니다.

dp 배열

i	0	1	2	3	4	5	6	7	8	9
값	2	3	-1

4. 새로 시작하는 것이 더 유리할 때는 과감히 선택해야 합니다.

네 번째 위치 i=3에서 두 가지 선택지를 비교합니다.

• 연속 유지: dp[2] + arr[3] = -1 + 3 = 2
• 새로 시작: arr[3] = 3

새로 시작하는 것이 3 > 2로 더 유리하므로 새로 시작합니다.

dp 배열

i	0	1	2	3	4	5	6	7	8	9
값	2	3	-1	3

5. 연속을 유지하는 것이 여전히 유리하다면 그대로 유지합니다.

다섯 번째 위치 i=4에서 두 가지 선택지를 비교합니다.

• 연속 유지: dp[3] + arr[4] = 3 + 4 = 7
• 새로 시작: arr[4] = 4

연속을 유지하는 것이 7 > 4로 더 유리하므로 연속을 유지합니다.

dp 배열

i	0	1	2	3	4	5	6	7	8	9
값	2	3	-1	3	7

6. 연속을 유지하는 것이 더 낫다면 계속 이어갑니다.

여섯 번째 위치 i=5에서 두 가지 선택지를 비교합니다.

• 연속 유지: dp[4] + arr[5] = 7 + (-4) = 3
• 새로 시작: arr[5] = -4

연속을 유지하는 것이 3 > -4로 더 유리하므로 연속을 유지합니다.

dp 배열

i	0	1	2	3	4	5	6	7	8	9
값	2	3	-1	3	7	3

7. 연속을 유지하는 것이 크게 유리할 때도 있습니다.

일곱 번째 위치 i=6에서 두 가지 선택지를 비교합니다.

• 연속 유지: dp[5] + arr[6] = 3 + 6 = 9
• 새로 시작: arr[6] = 6

연속을 유지하는 것이 9 > 6으로 더 유리하므로 연속을 유지합니다.

dp 배열

i	0	1	2	3	4	5	6	7	8	9
값	2	3	-1	3	7	3	9

8. 최대값을 더 크게 만들어갈 수 있습니다.

여덟 번째 위치 i=7에서 두 가지 선택지를 비교합니다.

• 연속 유지: dp[6] + arr[7] = 9 + 5 = 14
• 새로 시작: arr[7] = 5

연속을 유지하는 것이 14 > 5로 더 유리하므로 연속을 유지합니다.

dp 배열

i	0	1	2	3	4	5	6	7	8	9
값	2	3	-1	3	7	3	9	14

9. 손해가 있더라도 연속을 유지하는 것이 더 낫습니다.

아홉 번째 위치 i=8에서 두 가지 선택지를 비교합니다.

• 연속 유지: dp[7] + arr[8] = 14 + (-5) = 9
• 새로 시작: arr[8] = -5

연속을 유지하는 것이 9 > -5로 더 유리하므로 연속을 유지합니다.

dp 배열

i	0	1	2	3	4	5	6	7	8	9
값	2	3	-1	3	7	3	9	14	9

10. 연속을 유지하여 마무리합니다.

열 번째 위치 i=9에서 두 가지 선택지를 비교합니다.

• 연속 유지: dp[8] + arr[9] = 9 + 1 = 10
• 새로 시작: arr[9] = 1

연속을 유지하는 것이 10 > 1로 더 유리하므로 연속을 유지합니다.

dp 배열

i	0	1	2	3	4	5	6	7	8	9
값	2	3	-1	3	7	3	9	14	9	10

전체 코드

#include <iostream>

using namespace std;

int max_find(const int* arr, const int size)
{
    int val = -200000;
    for (int i = 0; i < size; i++)
    {
        if (arr[i] > val)
        {
            val = arr[i];
        }
    }
    return val;
}

int main(void)
{
    int arr[100000], dp[100000] = {0, };
    int N, max_val = -200000;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }

    dp[0] = arr[0];

    for (int i = 1; i < N; i++)
    {
        dp[i] = max(dp[i - 1] + arr[i], arr[i]);
    }

    max_val = max_find(dp, N);
    cout << max_val << endl;

    return 0;
}

개별 코드 설명

dp[0] 초기화

첫 번째 값은 선택의 여지가 없기 때문에, dp[0] = arr[0]으로 초기화합니다.
초기 상태 표:

i	0	1	2	3	…
arr	2	1	-4	3	…
dp	2				…

점화식

반복문 안에서 dp[i] = max(dp[i-1] + arr[i], arr[i]);를 사용합니다.
이 점화식은 “이전까지의 연속합에 현재 값을 더해 연속을 유지하는 것이 유리한지, 현재 값 하나로 새로 시작하는 것이 유리한지”를 결정합니다.

예시 표 (i=1 이후):

i	0	1	2	3
arr	2	1	-4	3
dp	2	3

최대값 찾기

dp 배열에는 각 위치에서 끝나는 연속합의 최대값이 저장되어 있습니다.
max_find() 함수는 dp 배열 중 가장 큰 값을 찾아 반환합니다.

예제 입력:
2 1 -4 3 4 -4 6 5 -5 1

계산된 dp 배열:

i	0	1	2	3	4	5	6	7	8	9
dp	2	3	-1	3	7	3	9	14	9	10

이 중에서 가장 큰 값은 14입니다.
출력값은 14가 됩니다.

결론

• 동적 계획법(DP)을 사용하여 연속합 문제를 효율적으로 해결할 수 있습니다.
• 매 단계마다 연속을 유지할지 새로 시작할지를 비교해 최적의 선택을 합니다.
• dp 배열에 각 위치까지의 최적 연속합이 저장됩니다.
• dp 배열 중 최댓값을 선택해 출력하면 됩니다.

원하시면 추가로 다른 테스트케이스나 표를 더 작성해 드릴 수 있습니다. 말씀해 주십시오.