[Baekjoon] 1912번: 연속합

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

1912번: 연속합

 

---

 

문제 해결 과정

착안

주어지는 임의의 수열 내의 연속된 숫자들의 합 중에서 가장 큰 값을 찾아야하는데, 이때 몇 개의 연속된 숫자의 합이 최대일지는 알 수 없으므로 반복적으로 연속합을 구하고 비교하는 것을 요구한다. 따라서 기존에 구해놓은 연속합의 값을 저장하고, 추가적인 연속된 숫자를 입력받으면 더해서 비교한 뒤 필요하면 다시 저장하여 사용하는 방식으로 동적계획법(dynamic programming) 알고리즘을 구상하고자 하였다.

 

구현

처음에는 우선 수열 전체를 저장하고, 연속합을 계산하는 메커니즘을 별도로 구현했다. 나름 머리를 써본답시고 저장하는 수열의 크기를 줄이고자 입력을 받을 때 0보다 큰 수가 연속으로 입력되는 경우, 그 수들을 합쳐서 하나의 항으로 만들어 저장하고자 해보았는데 나중에 연속합의 최댓값을 찾는 과정을 구현하면서 굳이 수열을 저장하지 않아도 된다는 것을 깨달아 알고리즘을 수정하였다.

 

연속합을 계산하고 비교할 때, 이전에 계산하여 저장한 연속합의 값만 있으면(메모이제이션, memoization) 새로 입력받는 숫자와 기존의 연속합의 값 사이의 연산만으로도 문제를 해결할 수 있었다(아래 참고).

 

\(n-1\)번째 루프까지 구한 연속합의 최댓값을 max, 연속합의 값을 \(M_{n-1}\),  \(n\)번째 루프에서 입력받은 수를 \(a_{n}\)이라고 하면,

 

• i) 연속합의 최댓값 갱신:  \(a_{n} >\) max인 경우 : max \(= a_{n}\)
• ii) 연속합의 값 메모이제이션:  \(M_{n} = M_{n-1} + a_{n}\)
  • 1) \(M_{n} > 0\)인 경우, 연속합의 최댓값을 갱신:  \(M_{n} >\) max 이면 max \(= M_{n}\)
  • 2) \(M_{n} \leq 0\)인 경우, 메모이제이션 값을 0으로 초기화:  \(M_{n} = 0\)

 

의 과정을 반복하여 수열 내의 연속합 중에서 가장 큰 값을 찾을 수 있었다.

 

위의 과정을 머리로 생각해보고 코드로 도출해내는 부분이 조금 어려웠다. 어째서 위와 같은 방식으로 계산이 되어야하는지 이해가 잘 되지 않는다면 다음 예시를 참고하면 좋을 것 같다.

 

수열의 가장 왼쪽의 수 \(a_{1}\)부터 시작하여 \(n-1\)번째 수인 \(a_{n-1}\)까지 모두 0보다 크다고 가정하면,  \(M_{n-1} > M_{1}, M_{2}, \cdots, M_{n-2}\) 이며 이때까지의 max \(= M_{n-1}\) 이다.

이때 \(n\)번째로 입력받은 수가 \(a_{n} < -M_{n-1}\)이면 \(n\)번째 수까지 포함하는 연속합 \(M_{n} = M_{n-1} + a_{n} < 0\) 이다. 이는 수열에서 연속합의 최댓값을 찾을 때 \(a_{n}\)을 기준으로, 이 숫자보다 왼쪽에 있는 수들끼리 연속합을 구했을 때, 또는 오른쪽에 있는 수들끼리 연속합을 구했을 때만 최댓값이 될 수 있다는 의미이다. 즉, 수열 내에서 연속합을 구할 때 \(a_{n}\)이 포함되면 최댓값이 될 수 없다는 뜻이다.

따라서 기존에 \(1, 2, \cdots, n-1\) 번째 수를 이용해 계산한 연속합의 최댓값 max는 그대로 두고, \(M_{n}\)의 값을 0으로 초기화해버린 다음 다시 \(a_{n+1}\)번째 수부터 연속합을 구하는 과정을 수행하면 문제를 해결할 수 있다.

 

한편, 입력이 빈번하게 일어나는 문제이므로 C++ 표준 입출력 스트림의 속도 최적화 코드를 사용해보았다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, k, max, memoize;
	cin >> n >> k;
	max = memoize = k;
	n--;

	while (n--)
	{
		cin >> k;
		if (max < k)
			max = k;

		if (memoize + k > 0)
		{
			memoize += k;
			if (max < memoize)
				max = memoize;
		}
		else
			memoize = 0;
	}
	
	cout << max << "\n";

	return 0;
}

 

실행 결과

처음 제출 결과에서는 착안이 어려워 비효율적으로 수열을 전부 저장해서 해결하였는데, 이 때문에 메모리를 더 많이 사용했다.