[알고리즘] 백준 온라인 저지 BOJ 1912 : 연속합

1912번 연속합

문제 해석

---

수열에서 연속된 수들의 합이 가장 큰 것을 구하는 문제입니다.

10, -4, 3, 1, 5, 6, -35, 12, 21, -1 라는 수열에서 가장 큰 연속은 얼마일까요?

12, 21 부분이 가장 큰 연속합입니다.

연속합의 수들은 한개 이상이라는 점입니다.

제약 조건

---

100,000개의 수들이 주어지고 각각의 수는 -1000~1000의 크기를 갖습니다.

풀이

---

음

쉬워보입니다.

처음 시작점을 고정하고 끝점을 하나씩 늘려가면서 시작점과 끝점을 전부 더하는 거죠. 전부 현재의 최대값과 비교해서 크면 그게 최대값이 되는 식으로요.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int nums[100001];

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &nums[i]);

	int ans = -1001;
	for (int start = 0; start < n; start++) {
		for (int end = start; end < n; end++) {
			int sum = 0;
			for (int i = start; i <= end; i++)
				sum += nums[i];
			ans = max(sum, ans);
		}
	}
	printf("%d\n", ans);
}
	

네, 이렇게 제출하면 시간초과랍니다. 하하

입력이 자그마치 10만개가 되거든요.

단순히 이렇게 for루프만 돈다면 문제를 해결할 수가 없습니다.

여기서 간단한 이론(?)이 있는데요.

부분합이라는 개념이 여기 사용됩니다.

우리는 전에 계산한 합을 이용할 수 있다는 거죠.

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
10	-4	3	1	5	6	-35	12	21	-1
10	6	9	10	15	21	-14	-2	19	18

[0]~[5]까지의 합은 [0]~[4]까지의 합 + 현재의 수를 더하면 된다는 것을 알 수 있습니다.

코드로 본다면 이런 형태이죠.

for (int i = 1; i <= n; i++)
		partialSum[i] = partialSum[i - 1] + numbers[i];

i가 1부터 시작한 이유는 조금 더 보기 편하게 하기 위함입니다. 그러니까 n까지 for루프를 돌아야 됩니다.

그렇다면 [7]~[8]까지의 합만을 구하려면 어떻게 할까요?

partialSum[8]-partialSum[6]을 하게 되면 [7]과 [8]의 부분합만을 구할 수 있습니다.

그럼 1부터 3까지의 합은 partialSum[3]-partialSum[0]이 되겠죠? 인덱스를 왜 1부터 시작하는 지 이유를 알 것 같습니다. 그렇지 않으면 if문을 사용해야합니다.

이제 우리는 위의 코드를 2개의 for문으로 줄일 수 있습니다.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int partialSum[100001];

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int number;
		scanf("%d", &number);
		partialSum[i] = partialSum[i - 1] + number;
	}
	int ans = -1001;
	for (int start = 0; start <= n-1; start++) {
		for (int end = start + 1; end <= n; end++) {
			ans = max(ans, partialSum[end] - partialSum[start]);
		}
	}
	printf("%d\n", ans);
}
	

부분합을 이용해서 이중 for문으로 문제에 접근할 수도 있지만, 이 역시 시간초과가 됩니다. 아까 말한것 처럼 입력이 10만개이기 때문에 이중 for문 역시 시간초과죠.

여기서 한 번 더 줄일 수 없을까요?

부분합을 이용해서 말이죠. 

그전까지 계산한 부분합 + 지금 숫자가 지금 숫자보다 작다면 부분합은 다시 계산 되어야 한다는 것을 직관적으로 느낄 수 있을까요??

그러니까...

현재의 수를 numbers[i]라고 하고 그 전까지 계산했던 부분합이 partialSum[i-1]라고 할때 , partialSum[i]=max(partialSum[i-1]+numbers[i], numbers[i]) 라고 하는 것 말이에요.

다시말해,

partialSum[i]=max(partialSum[i-1]+numers[i], numbers[i])

                =max(지금까지의 부분합, 현재 수)

라고 하는 것이 이해가 가시나요?

지금까지 구한 부분합이 현재의 수보다 작다면 현재의 수부터 다시 부분합을 계산하는 것이 더 클 거니까요.

이것만 이해가 간다면, 다음의 코드는 이 과정을 배열없이 구현했다라는 것을 알 것입니다.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n, partialSum = 0, maxPartialSum = -1001;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		int number;
		scanf("%d", &number );
		partialSum = max(number, number + partialSum);
		maxPartialSum = max(partialSum, maxPartialSum);
	}

	printf("%d\n", maxPartialSum);
	
}
	

코드가 무척이나 짧아졌습니다.

문제의 답은 maxPartialSum입니다. 

코드에서 이 부분을 보세요.

partialSum = max(number, number + partialSum);

number는 현재의 수를 말하는 것이고, partialSum은 이전까지 계산했던 부분합을 의미합니다.

현재의 수와 이전까지 계산했던 부분합 + 현재의 수가 현재의 수보다 작다면 부분합은 다시 현재의 수부터 시작입니다.

이후 이 부분합(partialSum)과 지금까지 부분합의 최대값(maxPartialSum)을 비교해서 큰 값이 다시

maxPartialSum이 되는 것입니다.