[C++] 백준 1912번 연속합

1. 문제이해

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

n개의 정수로 이루어진 수열이 주어진다.

이 중 연속된 몇 개의 숫자를 선택해 구할 수 있는 합 중 최댓값을 출력하는 것이 목표이다.

 

 

 

2. 문제이해

 

저는 시간초과가 너무 싫어요...^^

문제풀이를 보시는 분들이라면 아마 아시겠지만,

역시나 모든 경우의 수를 따져 합을 비교하고 구하면 시간초과가 발생한다.

필자는 첫 번째로 이중 for문을 통해 모든 경우의 합을 구하고 비교했으나, 시간초과가 발생했다.

따라서 다른 방법으로 고안해낸 것이 바로 다이나믹 프로그래밍 (DP) 이다.

 

수열에 포함된 각 정수들을 v[i], 수열의 i 번째 정수의 경우 만들 수 있는 최대 합을 DP[i] 라고 하자.

예제 입력 3의 경우, 수열의 크기는 5, 수열에 포함된 정수는 -1 -2 -3 -4 -5 이다.

 

1. 첫번째 정수인 -1 까지 만들 수 있는 최대 합은 해당 정수값인 -1 밖에 없으므로, DP[0] = 1

 

2. 2번째 정수인 -2 까지 만들 수 있는 최대 합을 구해보면, -1 + -2 = -3 또는 -2 이다.

둘 중 더 큰 값은 자기 자신인 -2 이므로, DP[1] = -2

 

3. 3번째 정수인 -3 까지 만들 수 있는 최대 합을 구해보면,

2번째 값까지 만들 수 있는 최댓값 + (-3) = -5 또는 -3 이다.

둘 중 더 큰 값은  -3 이므로, DP[2] = -3 이다.

 

 .

.

.

 

위 풀이법을 조합해보면, DP[i]는 다음과 같이 정의할 수 있다.

DP[i] = max (DP[i - 1] + v[i] , v[i])

즉, i번째 정수의 경우 만들 수 있는 최대 합은

그 전 정수(i - 1)의 경우 만들 수 있는 최댓값 + 자기 자신, 혹은 자기 자신 중 하나이다.

 

위와 같이 각 정수에서 만들 수 있는 최대합을 모두 구하면,

이들(DP[i]) 중 가장 큰 값이 연속된 숫자들을 이용해 구할 수 있는 가장 큰 값이 된다.

 

 

 

3. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	vector <int> v;
	vector <int> dp;
	int N;
	int input;
	int max_sum;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;
		v.push_back(input);
	}

	dp.push_back(v[0]);
	max_sum = v[0];
	// 해당 정수값까지 만들 수 있는 최대 합(DP[i]) 구하기
	for (int i = 1; i < N; i++) {
		dp.push_back(max(dp[i - 1] + v[i], v[i]));

		// 기존 최대합 값과 해당 정수에서의 최대 합을 비교
		// 더 큰 값을 채택해 초기화
		max_sum = max(dp[i], max_sum);
	}

	cout << max_sum;

	return 0;
}

2. 문제풀이에서 도출한 방법에 따라 작성한 코드이다.

수열에 포함된 각 정수들을 v[i], 수열의 i 번째 정수의 경우 만들 수 있는 최대 합을 dp[i] 라고 선언 후,

dp[0], max_sum 값을 v[0]으로 초기화해준다.

(첫 번째 정수까지 만들 수 있는 최대 합은 자기자신의 경우밖에 없기 때문에 dp[0] = v[0]

max_sum은 최종적으로 구하고자 하는 구할 수 있는 합 중 가장 큰 합으로,

아래 for문을 통해 각각의 dp[i] 값과 비교, 더 큰 값으로 해당 값을 초기화한다.

먼저, dp[0]값과 동일한 v[0] 값으로 초기화 해둔 후 아래 연산을 시작한다.)

for문에서는 위에서 도출한 식인 DP[i] = max (DP[i - 1] + v[i] , v[i]) 을 이용해

각 정수값까지 만들 수 있는 최대 합을 구해주었다.

dp[i] 값을 구한 뒤에는 바로 기존 최대값(max_sum)과 비교, 더 큰 값을 max_sum 값으로 채택했다.

(dp[i] 중 가장 큰 값이 수열에서 연속된 몇개의 정수를 채택해 만들 수 있는 최대값(max_sum) 값이 된다.)

 

 

---

백준에서는 정말 조금만 방심하면 시간초과가 나는 것 같다..😥

왠지 조금이라도 돌아가는 것 같다..? 라는 느낌이 들면 아니나 다를까..

원래 시간초과가 난 이중 for문 코드도 포스팅에 넣고 싶었지만,

비슷한 문제를 겪으신 분들이 이미 많을 것이라고 생각하고 넣지 않았다.

언제나 새롭고 효율적인 알고리즘을 생각하는 것은 어렵다..✍