[백준] 1912번 : 연속합

문제

 

---

풀이

 

이것도 유명한 동적계획법 문제인데...

그냥 뭐 간단하게 생각해서 이런 수열이 있다고 하자

5, -8, 9, -1, ...

 

당연히 처음은 0으로 시작할 것이다. 0+5를 해서 5가 나왔고 다음 숫자를 보니 -8이다. 5+(-8) = -3인데, 우리가 0으로 시작했다는 걸 생각하면 굳이 이 -3을 안고갈 이유는 없다. 그래서 여기서 연결을 끊고 다시 0부터 시작한다. 0+9를 해서 9가 나왔고, 그 다음이 -1이지만 9에서 -1을 더해도 8이고, 뭐 그 뒤에 10이 나올 수도 있는거니까 연결을 끊지않고 계속 이어나간다.

 

간단히 말하자면 연속합이 음수가 되는순간 연결을 끊고 다시 시작하는 것이다.

다만 모든 입력이 음수인 경우가 있을 수 있다. 코드를 작성할 때 이 부분을 잊지 말아야 한다.

---

소스코드

 

#include <iostream>
using namespace std;

int main() { //배열쓰면 시간초과될듯?
    int max = -1001, current_sum = 0;
    int input, n;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> input;
        if (current_sum + input >= 0) {
            current_sum += input;
            if (current_sum > max) //지금까지의 연속합이 최댓값보다 크면 갱신
                max = current_sum;
        }
        else {
            current_sum = 0; //이번 입력을 더하면 음수가 되는 경우 연속 끊음
            if (input > max) //근데 전부 음수인 경우가 있을 수 있음
                max = input;
        }
    }
    cout << max;
}

현재까지의 연속합을 current_sum이라고 하고, 이번에 더할 값을 input이라고 한다.

만약 이 둘의 합이 양수인 경우에는 current_sum을 갱신하고, 최댓값 갱신여부도 확인한다.

음수인 경우에는 연결을 끊고 current_sum을 0으로 다시 초기화 한다. 다만 앞서말했듯 모든 input이 음수인 경우도 있으니 최댓값 갱신 여부는 확인해야 한다.