[백준] 13398번 : 연속합 2

문제

 

---

풀이

 

myunji.tistory.com/217

[백준] 1912번 : 연속합

이 문제에서 숫자를 하나 삭제할 수 있게 됐다.

 

그래서 del_sum이란 변수를 하나 추가한다. del_sum은 숫자를 삭제했을 수도 아닐 수도 있다.

특정 input이 들어왔을 때 del_sum에 들어올 수 있는 경우는 2가지다. 이 input을 사용하거나 삭제하거나.

input을 사용할 때는 del_sum = del_sum+input이다.

input을 버릴 땐 del_sum을 사용할 수 없으니 이전 input까지의 sum이 del_sum이 될 것이다.

 

40 -30 3 1 5 -29 12 -1

이란 데이터가 있다고 하자.

 

	40	-30	3	1	5	-29	12	-1
0
0

위에서부터 input, sum, del_sum이다.

sum과 del_sum은 0으로 초기화 해놓았고 del_sum부터 갱신할 것이다.

경우에 따라 이전 input까지의 sum을 del_sum으로 갱신해야 할 때가 있기 때문에 del_sum을 먼저 갱신하는 것이다.

 

	40	-30	3	1	5	-29	12	-1
0	40
0	40

먼저 del_sum을 갱신한다. 이번 input인 40을 사용한다면 del_sum은 40이 될 것이다.

사용하지 않는다면 기존의 sum인 0이 될 것인데, 당연히 0보단 40이 크기 때문에 40으로 갱신된다.

 

sum을 갱신하는 과정은 1912번 풀이와 같다.

sum+input>=0이기 때문에 sum = sum+input이다.

 

	40	-30	3	1	5	-29	12	-1
0	40	10
0	40	40

input=-30에 대해 del_sum은 del_sum+input=10보다 sum인 40이 더 크기 때문에 이전의 sum을 복사해온다.

sum은 sum+input>=0이기 때문에 10으로 갱신된다.

 

계속 하다보면

	40	-30	3	1	5	-29	12	-1
0	40	10	13	14	19
0	40	40	43	44	49

input=-29의 순간이 온다.

먼저 del_sum을 갱신한다. del_sum+input = 20이다. 그리고 sum은 19이다.

del_sum+input이 sum보다 크기 때문에 20으로 갱신한다.

 

sum은 sum+input<0이기 때문에 0으로 초기화 한다.

 

	40	-30	3	1	5	-29	12	-1
0	40	10	13	14	19	0	12	11
0	40	40	43	44	49	20	32	31

답은 49가 된다.

 

다른 풀이들을 봤는데 dp 배열에 sum과 del_sum을 저장하는 것을 볼 수 있었다.

근데 바로 직전 값만 참조하기 때문에 굳이 그럴 필요 없다.

---

소스코드

 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int max_num = -1001, sum = 0, del_sum = 0;
    int input, n;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> input;
        del_sum = max(sum, del_sum+input); //이번 input 제거 or 사용
        if (sum + input >= 0) {
            sum += input;
            max_num = max(max_num, max(del_sum, sum));
        }
        else {
            sum = 0; //이번 입력을 더하면 음수가 되는 경우 연속 끊음
            max_num = max(max_num, input); //근데 전부 음수인 경우가 있을 수 있음
        }
    }
    cout << max_num;
}

모든 입력이 음수인 경우에 0을 출력하지 않도록 주의하자.