[백준/BOJ] 1912번 연속합 (C/C++)

백준 온라인 저지(BOJ) 1912번 연속합
https://www.acmicpc.net/problem/1912

1912번: 연속합

* 사용언어 : C언어, C++
 

1. 문제

n개의 정수로 이루어진 임의의 수열에서
연속된 수를 합하여 구할 수 있는 값 중 가장 큰 값을 출력

예를 들어, 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다면 정답은 12+21 = 33 이 됨

 

2. 풀이

우선 단순하게 브루트 포스 방식으로 전체 탐색을 해보면
아래와 같이 이중 for문으로 구현하여 해결할 수 있습니다.

// 중략
ret = -1000;
sum = 0;

for (int i = 0; i < n; ++i) {
	for (int j = i; j < n; ++j) {
		sum += arr[j];
		ret = max(ret, sum);
	}
	sum = 0;
}

printf("%d\n", ret);

이중 for문을 사용한 것에서 알 수 있듯이 시간 복잡도가 O(n^2) 이므로 좋은 방식이 아닙니다.

(그리고 이 코드로 완성하여 제출하면 시간초과로 오답입니다)
 

이 문제는 동적 계획법(Dynamic Programming)을 활용하여 O(n)의 시간 복잡도로 해결할 수 있습니다.
동적 계획법의 핵심은 직전에 계산한 결과값을 기억해두고 이를 활용하며 문제를 푸는 것입니다.
(동적 계획법의 더욱 적합한 명칭은 '기억하며 풀기' 입니다)
 
아래 예시로 해당 문제의 풀이법을 유도해보겠습니다.

3, 5, 6, -35, 12, 21, -1

1번까지의 연속합의 최대값은 [1번째 값(3)]인 3입니다. (여기서 3을 기억)
2번까지의 연속합의 최대값은 [직전에 기억한 최대값(3) + 2번째 값(5)]인 8입니다. (여기서 8을 기억)
3번까지의 연속합의 최대값은 [직전에 기억한 최대값(8) + 3번째 값(6)]인 14입니다. (여기서 14를 기억)
4번까지의 연속합의 최대값은 [직전에 기억한 최대값(14)]인 14입니다. (여기서 직전 최대(14) + 4번째 값(-35)인 -21을 기억)
  > 다음 자리(5번) 계산 시, 1 ~ 4번을 더하면 손해라는 것을 알 수 있도록 -21을 기억합니다.

5번까지의 연속합의 최대값은 [5번 값(12)]인 12입니다. (여기서 12를 기억)
   > -35를 포함하면 앞의 3, 5, 6 을 다 합쳐도 손해(-21)이므로 12를 기억하고 다시 시작합니다.
   > 추가로 현재까지의 최대값 14를 전체의 최대값이라고 ret 변수에 따로 기록해둡니다.
 
6번까지의 연속합의 최대값은 [직전에 기억한 최대값(12) + 6번 값(21)]인 33 입니다. (여기서 33을 기억)
   > 여기서 14가 12보다 크더라도 14를 사용하면 안됩니다.
   > 14는 -35(4번)로 연속이 끊기기 전까지의 최대값이고, 5번째 값(12)부터 다시 시작했으므로 12에서 시작합니다.
   > 추가로, 이번에 계산된 33이 기록해두었던 14보다 크므로 ret 를 33으로 바꿔줍니다.
 
7번까지의 연속합의 최대값은 [직전에 기억된 최대값(33) + 7번째 값(-1)]인 32입니다. (여기서 32를 기억)

따라서 이 수열의 최대 연속합은 33 (= 12 + 21) 이 됩니다.


위와 같이 문제를 풀고 일반화하여 정리하면 아래와 같습니다.

n번까지의 연속합의 최대값은 [n-1번까지의 최대값 + n번 값] or [n번 값] 둘 중 큰 값이다.

매번 계산되는 최대값은 dp[] 라는 배열에 기록하여 다음 번 연속합을 찾을 때 활용하고,
전체의 최대값은 ret 에 기록하여 계산된 값이 이를 초과하면 갱신합니다.
 
아래의 코드 참고하시어 index 가 하나하나 올라갈 때 어떻게 계산되는지 하나하나 생각해보시면
동적 계획법 소스 이해에 도움이 될 것 같습니다.
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1912_연속합
1892KB	16ms
*/
#include <cstdio>

const int LM = 100000;
int arr[LM], dp[LM], n, ret;

int max(int a, int b) {
	if (a > b) return a;
	return b;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d ", &arr[i]);

	ret = arr[0];
	dp[0] = arr[0];

	for (int i = 1; i < n; ++i) {
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);
		ret = max(dp[i], ret);
	}

	printf("%d\n", ret);
	return 0;
}