[백준 1912] 연속합

[백준 1912] 연속합

문제 출처 - https://www.acmicpc.net/problem/1912

---

문제

---

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

---

첫째 줄에 정수 n(1≤n≤100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

---

첫째 줄에 답을 출력한다.

예제 입력

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

예제 출력

33

• 문제 이해하기

임의로 준 N의 숫자만큼 입력하고, 이 중에서 연속된 숫자의 가장 큰 합을 구하는 문제다. 그냥 연속된 두 수만 비교해서 가장 큰 수를 출력하는 건 쉽게 느껴질 것이다. 하지만 이 문제의 포인트는 연속된 숫자의 수를 정해놓지 않았다.

즉, 연속된 4개의 수를 합한 것이 주어진 수 중에서 가장 크면 그 수를 출력해야 한다.

예시)

5 // 5개의 숫자 입력
3 -5 4 1 -2
 
 
출력 = 5 // 4 + 1이 연속된 가장 큰 수이다.

• 계획 및 문제 해결

우선 숫자들을 저장할 arr 배열을 생성한다. 정수 N은 1이상 10만 이하이므로 배열의 크기를 arr[100001]로 잡는다.

그리고 가장 큰 합을 구하기 위해 값을 저장할 dp 배열 하나를 더 만들자.

int arr[100001];
int dp[100001];

이제 메인 함수에 N의 수를 입력하고, N의 수 만큼 입력시키는 코드를 작성한다.

int N; // 입력할 N을 int형으로 선언
cin >> N; // N 입력
 
for (int i = 1; i <= N; i++) { 
// 1부터 N까지 반복문으로 배열에 수 입력
    cin >> arr[i];
}

이렇게 되면 arr 배열에 입력한 값이 저장될 것이다.

이제 가장 큰 합을 구하기 위해 dp배열을 통한 알고리즘을 만들어보자.

우리는 1부터 N까지 반복문을 돌렸기 때문에, dp[0] 값은 필요가 없다. 0으로 초기화하자.

dp[0] = 0;

dp[1]은 합할 것이 하나밖에 없기 때문에, arr[1] 값과 같다.

다음 배열부터는 아래와 같이 표현이 가능하다.

dp[2] = dp[1] + arr[2]
 
dp[3] = dp[2] + arr[3]
 
.
.
.
dp[N-1] = dp[N-2] + arr[N-1]
 
dp[N] = dp[N-1] + arr[N]
 

따라서, 반복문에서는 다음과 같이 표현할 수 있다.

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

하지만, 현재 이 dp배열 값은 크기 비교없이 해당 위치의 값까지 그냥 모두 더한 것이다. 만약 dp[i-1] 값이 음수라면, 그냥 arr[i]보다 크기가 작다. 따라서 이를 비교해줘야 연속된 수 중에서 가장 큰 값을 구할 수 있다.

따라서 두 가지로 나누어 작성해보자.

1. dp[i-1] + arr[i]가 arr[i]보다 크면?

dp[i] = dp[i-1] + arr[i];

2. dp[i-1] + arr[i]가 arr[i]보다 작거나 같으면?

dp[i] = arr[i];

이를 다시 정리하면 아래와 같다.

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];
        }
}

혹시 이해가 안될 수도 있기 때문에, 예시를 가지고 접근해보겠다.

기존 문제의 숫자가 너무 많으므로, 숫자 5개로 예시를 들었던 걸 다시 가져와보자

5 // 5개의 숫자 입력
3 -5 4 1 -2
 
arr[1] = 3
arr[2] = -5
arr[3] = 4
arr[4] = 1
arr[5] = -2

숫자 5개를 입력하면 arr배열에 다음과 같이 저장이 될 것이다.

이제 dp배열에 값이 저장되는 걸 하나씩 살펴보자.

dp[1] = arr[1] = 3 // dp[1]은 숫자 하나이기 때문에 arr[1]과 같다. 

dp[2] = dp[1] + arr[2] = 3 + (-5) = -2

dp[3] = dp[2] + arr[3] = 4 

// dp[2]이 음수라서, dp[2] + arr[3] < arr[3]이다. 따라서 dp[3] = arr[3]이 된다.

dp[4] = dp[3] + arr[4] = 4 + 1 = 5

dp[5] = dp[4] + arr[5] = 5 + (-2) = 3

가장 큰 값은 dp[4]의 5다. 따라서 이 문제에서 가장 큰 연속 합은 4 + 1이 되고, 출력값은 5를 나타내주면 된다.

int형 변수 max를 선언하고, 값이 저장되어있는 dp[1]부터 dp[N]까지 배열 번호를 증가시키면서 크기를 비교하고, 가장 큰 값을 max에 저장하는 방식으로 나타낼 수 있다.

int max = 0;
    max = dp[1]; // max값에 dp[1] 저장
 
    for (int i = 2; i <= N; i++) {
        if (max < dp[i]) {
            max = dp[i];
        }
    }

마지막으로 cout << max;를 통해 max 값을 출력시켜주면 문제를 해결할 수 있다.

• 전체 소스 코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int arr[100001];
int dp[100001];
 
 
int main(void)
{
    int N;
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    dp[0] = 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 = 0;
    max = dp[1];
 
    for (int i = 2; i <= N; i++) {
        if (max < dp[i]) {
            max = dp[i];
        }
    }
    
    cout << max;
 
 
    return 0;
}