4) 백준 1912 - 연속합

<문제>

www.acmicpc.net/problem/1912

1912번: 연속합

뭔가 될거 같은데 안된 문제. 개인적으로 답답- 했던 문제.

 

<코드>

#include <iostream>

using namespace std;

int main(void) {
	int num[100001] = {0, };
	int high[100001] = {0, };
	
	int N;
	cin >> N;
	
	int Max = -1000;
	for(int i = 1; i <= N; i++) {
		cin >> num[i];
	}
	
	int sum = 0;
	
	for(int i = 1; i <= N; i++) {
		sum += num[i];
		if(num[i] <= sum) {
			high[i] = sum;
		}
		else {
			high[i] = num[i];
			sum = num[i];
		}
	}
	
	for(int i = 1; i <= N; i++) {
		if(Max < high[i]) {
			Max = high[i];
		}
	}
	
	cout << Max << endl;
	
	return 0;
}

방법은 각 위치에서 최댓값을 저장하는데 규칙이 있다.

만약에 앞에서부터 계속 더해가는데 양수가 계속 나오면 문제는 없다. 그런데 음수가 나오면 조금 달라진다.

내 머릿속에서는 '처음에 음수가 나온다면 당연히 합이 작아지므로 새로 합을 구해야겠지...???' 에서 나온 문제들이다.

 

1. 음수가 나온 후에 뒤에서 계산을 했더니 최댓값이 더 커진다.

2. 음수가 나온 후에 뒤에서 따로 계산을 해야 더 큰값들이 나온다.

 

1.

예를 들어보자.

5 -1 6 7

위와 같은 수가 있는데 나의 처음 생각으로 접근해보면

값	5	-1	6	7
MAX	5		6	13

아래와 같은 결과가 나와서 MAX는 13이구나!! 라고 생각했다. 그런데!

값	5	-1	6	7
MAX	5	4	10	17

사실 답은 17이다. 이 경우를 생각해줘야 했다.

 

2.

예를 들어보자.

5 -35 6 7

1번과 같은 방법으로 하면 -35가 합을 엄청나게 줄이게 된다.

값	5	-35	6	7
MAX	5	-30	-24	-17

그래서

값	5	-35	6	7
MAX	5		6	13

-35에서 구간합을 초기화 시켜주고 다시 더해가야 한다.

 

이를 구분하는 방법은 현재 최댓값을 구해야 하는 곳의 값이 구간합보다 작다면!!! 1번의 경우로 가면 될것이고,

그게 아니라면!! 2번의 경우로 가면 된다.

 

하나의 예시가 맞으면 다른 예시가 틀리고 이게 반복되다보니 답답했던 문제였다...ㅠㅠㅠㅠㅠㅠ