[백준알고리즘] 1912번: 연속합 -C++

[백준알고리즘] 1912번: 연속합 -C++

1912번: 연속합 (acmicpc.net)

1912번: 연속합

주어진 수열에서 연속된 부분 수열을 뽑아냈을 때 가장 연속합이 큰 값을 구하면 된다.

 

예전에 파이썬으로 많이 풀었던 문제다. 그래서 그런가 이번에도 뭔가 아이디어가 쉽게 떠올랐다. 많이 인상 깊게 푼 문제였나 보다.

[백준알고리즘] 1912번: 연속합 -Python (tistory.com)

[백준알고리즘] 1912번: 연속합 -Python

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

해당 문제는 동적계획법(DP; Dynamic Programming)을 이용해서 풀었다. 

이전 원소까지의 최대 연속합을 이용해 현재 원소를 포함한 최대 연속합을 구하기 때문이다.

 

이게 무슨 말이냐면.. 말 그대로 차례대로 원소를 보면서 해당 원소를 포함한 최대 연속합을 구하는 것이다. 주어진 예제를 통해서 살펴보도록 하겠다.

 

10 -4 3 1 5 6 -35 12 21 -1

 

위의 예제에서 차례대로 연속합을 살펴보겠다. 먼저 첫 번째 원소를 포함한 연속 누적합은 일단은 \( 10 \) 일 것이다.

 

다음 \( -4 \)를 포함한 연속합을 살펴보겠다. 이때는 이전 이전까지의 연속합을 끊고 새로 시작하는 방법과 이전 연속합에 이어서 더하는 방법이 있다. 전자의 경우에는 연속합이 \( -4 \)가 될 것이다. 반면 후자의 경우에는 \( 10 + (-4) = 6 \)이 된다. 따라서 \( -4 \)를 포함한 최대 연속합은 \( 6 \)이 될 것이다.

 

마찬가지 방법으로 다음 원소들에도 적용해주면 된다. 그럴 경우 원소 \( 6 \)까지 각 원소를 포함한 최대 연속합은 아래와 같다.

 

10 6 9 10 15 21

 

이제 \( -35 \)가 포함된 원소를 살펴보도록 하겠다. 이전까지의 연속합을 끊고 새로 시작할 경우 연속합이 \( -35 \)가 될 것이고, 이전 연속합에 이어서 포함할 경우 연속합이 \( -14 \)가 될 것이다. 따라서 \( -14 \)가 최대 연속합이 될 것이다.

 

다음 \( 12 \)에 대해서도 마찬가지로 살펴보면 된다. 이전까지의 연속합을 끊고 새로 시작하는 경우의 연속합은 \( 12 \)이다. 반면, 이전 연속합에 이어서 포함할 경우에는 연속합이 \( -2 \)다. 따라서 최대 연속합은 \( 12 \)가 된다.

 

마찬가지 방법인 것이다.

 

결과적으로 아래와 같은 각 원소가 포함된 최대 연속합들을 나타나게 될 것이며, 이중 최댓값은 \( 33 \)이다.

 

10 6 9 10 15 21 -14 12 33 32

 

위와 같은 로직으로만 구현한 코드가 아래의 C++ 코드다.

#include <iostream>
#include <vector>
#include <algorithm>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<int> sequence(n);
	for (auto& element : sequence)
		std::cin >> element;

	int temp = -200000000;
	for (int i = 0; i < n; i++)
	{
		if (temp + sequence[i] < sequence[i])
		{
			temp = sequence[i];
			continue;
		}

		temp += sequence[i];
		sequence[i] = temp;
	}

	std::cout << *std::max_element(sequence.begin(), sequence.end());
}