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

유형	난이도	완료일	링크	특이사항
DP	실버2	23/02/16	https://www.acmicpc.net/problem/1912	오래 걸림, 질문게시판 참조

오답 코드

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

using namespace std;

int MAX = -9999;
int n;
int arr[100001];

bool exist[100001][100001];

void Recursion(int start, int end, int sum)
{
	if(start==end)
		return;

	if(sum > MAX)
		MAX = sum;
	
	exist[start][end] = 1;
	
		
	
	if(!exist[start+1][end])
		Recursion(start+1, end, sum-arr[start]);

	if(!exist[start][end-1])
		Recursion(start,  end-1, sum-arr[end]);
}

int main(void)
{ 
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;	
	
	int t;
	
	int start_sum=0;
	
	for(int i= 0; i<n;i++)
	{
		cin >> t;
		
		arr[i] = t;
		
		start_sum += t;
		
		if( t > MAX)
			MAX = t;		
	}
	
	Recursion(0, n-1, start_sum);
		
	cout << MAX;
}

처음엔 당연히 모든 경우의 합을 비교해야 한다고 생각하고, 그 합들을 어떻게 효과적으로 구할 것인지를 고민했다.

재귀함수로 중복되는 경우는 저장해두어 확인하려고 생각했지만 그러기 위해선 너무 큰 2차원 배열이 필요했다.

void MinusRecursion(int start, int end, int sum, bool right)
{
	if(end == start)
		return;
	
	if(sum > MAX)
		MAX = sum;
	
	if(right)
	{
		MinusRecursion(start, end-1, sum-arr[end],1);
	}
	else
	{
		MinusRecursion(start, end-1, sum-arr[end],1);
		MinusRecursion(start+1, end, sum-arr[start],0);
	}
}

재귀함수를 중복되는 경우의 계산이 없게끔 수정했다. n^2크기를 가지는 배열도 필요없어졌다.

모든 수의 합에서 시작하여 왼쪽 자식(현재 합 - 첫번째 숫자)은 오른쪽/왼쪽 자식 모두를 호출하고 오른쪽 자식(현재 합 - 마지막 숫자)은 계속 오른쪽 자식만 호출하는 방식으로 바꾼 것이다.

하지만 결국 n^2 * 1/2 정도 되는 모든 경우의 수만큼 재귀함수가 호출되는 것은 바뀌지 않는다. 여전히 시간복잡도는 O(n^2)인 것이다.

도대체 어떻게 해야 O(n)으로 시간 안에 해결할 수 있을지 모르겠어서 문제 관련 질문 게시판을 보던 중 Kadane 알고리즘에 대해 알게되었다.

부분합 문제 해결법이 카데인 알고리즘 자체였다. 카데인 알고리즘은 부분 합 문제를 O(n)에 푸는데 쓰인다. 이 알고리즘은 n+1 번째 까지의 합은 n번째 까지의 합에 n+1번째를 더한 것이라는 당연한 아이디어에서 출발한다.

합을 구하는 것이니 양수를 더하면 커질 것이고 음수를 더하면 작아진다. 계속 더한다고 합이 계속 증가하는 것이 아니다. 배열에 수열을 받았고 idx = 0 인 곳부터 +1씩 하며 array[i]까지의 합과 array[i]의 값을 비교하다보면, 어떤 지점에서 여태까지의 합을 포기하고(합이 음수가 되버린 경우일 것이다) 그 지점의 값 하나만을 취하는 것이 더 커질 수 있다는 것이다. 이런 지점을 발견하면 현재 최대 합은 array[i] 값으로 대체되고 이 값에 다시 다음 인덱스의 값들을 더해가며(부분합 수열의 길이가 1로 초기화 되는 것이다) 다시 더해진 값과 해당 인덱스 값을 비교하는 과정을 거친다. 이 과정에서 음수를 만나 더하게 되면 처음 최댓값이 대체되었을 때의 값보다 현재 최대 합이 작아지게 된다. 따라서 한 번 최대를 기록한 값을 저장해두기 위한 변수가 따로 필요하다. 이 과정을 배열의 마지막 인덱스까지 거치고 나면 최댓값들 중 가장 컸던 값이 부분합 중 최대의 값이 된다.

최대 합이 무엇인지를 찾는 것이니 모든 합을 구할 필요조차 없다.() 탐색을 하면서 역대 최대 합이 무엇인지, 최대 값 발견 지점부터 i까지 더했을 때 현재의 최대 합이 무엇인지 두 가지 변수만 갱신해가면 된다.

정답 코드

#include <iostream>

using namespace std;

int MAX = -9999;
int n;
int arr[100001];

int main(void)
{ 
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	
	cin >> n;	
	
	int t;
	
	for(int i= 0; i<n;i++)
	{
		cin >> t;
		
		arr[i] = t;
		
		if( t > MAX)
			MAX = t;		
	}
	
	//카데인 알고리즘
	int temp_max = arr[0];
	
	for(int i=1; i<n; i++)
	{	
		temp_max += arr[i];
		
		if(temp_max < arr[i])
			temp_max = arr[i];
		
		if(MAX < temp_max)
			MAX = temp_max;
	}
	//////////////////////////
	cout << MAX;
}

부분합 수열의 길이가 1,2,3, … , n 즉 n개 만큼이나 다양하고 그 합들도 이전 합으로 쉽게 구해지긴 하나 값들이 다 달라 구해야만 할 것이라고 생각하니 머릿속에 O(n^2)의 브루트포스 방식 말고는 그려지지가 않았다. 카데인 알고리즘을 찾아보지 않았더라면 나 스스로 생각해내기는 쉽지 않았을 것이다.

간단한 알고리즘임에도 내 직관과는 많이 다른 방식의 풀이여서 생각이 잘 나지 않은 것 같다. 아직 많이 부족함을 느끼게 해준 문제다.