02.01. 연속합[Brute-force Search][백준 1912]

 

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

1912번: 연속합

Algorithm classification : Dynamic programming

 

이 문제는 추후에 배울 DP문제이지만 Brute-force로 풀면 실패하는 것을 보이기 위해 이 문제를 선정하였습니다. 생각해보니 아예 틀렸네요. 시간초과로 나온다는 것을 보여드리고 싶었는데...

02.01.1. Problem

Given an arbitrary sequence of n integers. We try to find the largest sum of possible sums by selecting several consecutive numbers among them. However, more than one number must be selected. For example, given the sequence 10, -4, 3, 1, 5, 6, -35, 12, 21, -1. Here, the correct answer is 33, which is 12 + 21.

 

02.01.2. Input limit

The first line is given an integer n (1 ≤ n ≤ 100,000) and the second line is a sequence of n integers. number is an integer greater than or equal to -1,000 and less than or equal to 1,000.

 

02.01.3. Output

첫째 줄에 답을 출력한다.

 

02.01.4. Solution

	ans = dp[0] = data[0];
	for(i = 1; i <= j; i++){
		dp[i] = max(dp[i-1] + data[i], data[i]);
		ans = max(ans, dp[i]);
		//printf("%d ",dp[i]);
	}

핵심은 dp[i] = max(dp[i-1] + data[i], data[i]); 입니다. 이 식에 대한 자세한 설명은 DP 글에서 다시 다루도록 하겠습니다. 이전 글에서 데이터를 입력받을 때 미리 처리할 수 있는 부분이 있으면 처리하는 것이 좋다고 하였습니다. 양수면 어차피 부분수열의 후보에 들테니 미리 더해 놓는 것도 하나의 방법이죠. 그 이유는 dp[i] = max(dp[i-1] + data[i], data[i]);식에서 찾아볼 수 있습니다. 한번 고민해보시죠. 간단한 예로 -1 2 3 -1 4라는 data set이 있다고 가정한다면, -1 5 -1 4로 전처리를 한 것과 결과는 같겠죠. 이렇게 하면 DP에서 순회할 j의 SIZE가 줄어들게 될 것입니다.

	for(i = 1; i < n; i++){
		scanf("%d", &t);
		if(t >= 0){
			if(data[j] < 0) j++;
			data[j] += t;	
		}
		else
			data[++j] = t;
	}

 

문제를 직접 풀어볼 여러분들을 위해 놓치기 쉬운 몇 개의 data set를 적어두겠습니다. 비록 도움되길 바라겠습니다.

 

Case 1

12
10 -1 -1 -1 17 2 1 -4 -3 19 1 -4

 

만약, 여러분이 저의 아이디어를 두고 -1 -1 > -2로 음수도 묶겠다는 아이디어를 생각하셨다면 훌륭합니다. 5 -1 -1 3과 같은 data set에서는 5 -2 3으로 처리하는 것이 타당해 보이죠. 하지만 아래의 data set에서 오답을 출력할 것입니다.

	for(i = 0; i < n; i++){
		scanf("%d", &t);
		if(t * data[j] >= 0)
			data[j] += t;
		else
			data[++j] = t;
	}

Case 2

5
-1 -2 -3 -4 -5