[BOJ] 1912 - 연속합 (C++)

1. 문제

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

1912번: 연속합

• 양의 정수 n(1 ≤ n ≤ 100,000)과 n개의 원소로 이루어진 수열 An이 주어진다.
• 이때, An에서 가장 큰 구간합을 구하여라.

2. 해결 방법

1. Brute Force

먼저 가장 간단한 방법은, Brute Force 방식으로 크기 n의 int 배열을 만들어 i번째 자리에서 1~i-1번째 자리부터에서의 합을 구해 O(n^2)(1~i에서 O(n), 이를 1번째부터 i-1까지 반복하므로 O(n^2)), 만약 그게 maxVal보다 크면, maxVal을 업데이트해주는 방식을 생각해볼 수 있다. 이를 모든 원소마다 반복하므로 총 시간 복잡도는 O(n^3)이 된다.

for(int i = 0; i < n; i++){
	for(int j = 0; j <= i; j++{
		sectionSum = 0;
		for(int k = j; k <=i; k++{
			sectionSum += arr[k];
		}
		maxVal = max(sectionSum, maxVal);
	}
}

만약 구간합을 사용하면, 합을 구하는 과정에서의 시간복잡도를 O(1)으로 줄여 총 시간 복잡도를 O(n^2)으로 만들 수 있다.

// arr은 구간합 저장하는 배열
for(int i = 0; i < n; i++){
	for(int j = 0; j <= i; j++{
		if(j == 0) sectionSum = arr[i];
		else	sectionSum = arr[i] - arr[j - 1];
		maxVal = max(sectionSum, maxVal);
	}
}

 

2. 구간 합

구간 합 아이디어를 이용해 O(n) 내에 문제를 해결하려고 한다면, 다음과 같은 생각을 해볼 수 있다.

먼저, arr[] 배열에는 구간합을 저장한다.

 

i번째 자리에서 1~i-1까지의 모든 구간합을 비교해주기보다, 그중 가장 작은 구간합 하나를 미리 정하고 가져와서 이를 현재 자리에서 빼주기만 한다면 O(1)만에 A[i]까지의 최대 구간합을 구할 수 있다.

 maxVal = max(max(maxVal, arr[i] - minVal), arr[i]);
 minVal = min(minVal, arr[i]);

maxVal을 정할 때, 기존의 최대 구간합 maxVal이랑, 현재까지의 구간합 arr[i], 현재 구할 수 있는 최대 구간합 arr[i] - minVal 이 세 가지와 비교해줘야 한다.

arr[i] - minVal이 있는데도 arr[i]랑 추가로 비교해주는 이유는, minVal > 0이라면, 오히려 A1부터 Ai까지 더한 arr[i] 값이 더 커지기 때문이다.

 

그리고 최소 구간합을 현재 자리의 구간합 arr[i]와 비교해서 만약 arr[i] < minVal이라면, minVal을 업데이트시켜주기만 하면 된다.

 

3. DP

dp 방식을 사용해 문제를 해결할 수도 있다.

다만, 구간합 방식과는 차이가 있는데,

일단 다음과 같은 점화식을 사용한다.

dp[i] = arr[i] + dp[i - 1];

다만, dp[i-1] < 0인 경우에는 dp[i]에는 arr[i]값만 저장한다.

이전까지의 합이 음수일 경우, dp[i]에 저장할 이유가 없기 때문이다.

 

최종적으로는 dp[] 배열을 한 번 돌면서 max값을 출력해 주거나, 또는 위의 dp[i]를 정하고, for문에서 바로바로 max값이랑 비교해 줘도 된다.

3. 배운 점

구간합과 DP에 대한 이해도를 더 키울 수 있었다.

특히, 현재까지의 모든 구간합의 조합이라고 생각하기보다, 최소 구간합 부분을 하나 저장하여 이를 사용하는 것이 효율적이라는 아이디어를 얻을 수 있었다.

4. 코드