04.02. 부분배열 고르기[Divide and conquer][백준 2104]

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

2104번: 부분배열 고르기

 

Algorithm classification : Divide and conquer, Strack, Data structure, Segment tree

 

04.02.1. Problem

One-dimensional array A[1], … of size N (1 ≤ N ≤ 100,000). , A[N]. The score for any i, j (1 ≤ i ≤ j ≤ N) is (A[i] + … + A[j]) × min{A[i], … , A[j]}. That is, the sum of i to j multiplied by the minimum value from i to j is the score.

Given an array, write a program that picks out the subarray with the highest score.

 

04.02.2. Input limit

The first line is given an integer N. The next line contains A[1], … , given integers representing A[N]. Each integer has a non-negative value and does not exceed 1,000,000.

 

04.02.3. Output

Print the maximum score on the first line.

 

04.02.4. Solution

분할정복 개념만 머리에 박아둔 상태로 문제에 접근하다가는 모든 경우를 고려하지 못할 수도 있는 문제입니다. 처음 접하는 분들께는 조금 어려운 문제가 될 수도 있습니다. 계속 문제를 나누면 되는데 이때 조심해야 할 것은 정답이 나누는 기점을 포함하여 나눈 양쪽에 걸치는 경우에 포함될 수도 있다는 것입니다. 즉, 3가지 경우를 고려해야 하는 거죠.

long long int cal(int s, int e){
	if(s == e) return datab[s] * datab[s];
	//if(s+1 == e) return (datab[s] + datab[e]) * min(datab[s], datab[e]);
	int mid = (s+e) / 2;
	long long int temp1, temp2;
	temp1 = cal(s, mid);
	temp2 = cal(mid+1, e);
	long long int result = max(temp1, temp2);
	
	long long int temp, mintemp;
	int i, j, k;
	i = mid; j = mid + 1;
	temp = datab[i] + datab[j];
	mintemp = min(datab[i], datab[j]);
	result = max(result, mintemp * temp);
	while(s <= i && j <= e){
		if((s == i && j <= e + 1) || (j <= e + 1 && s + 1 <= i && datab[i-1] < datab[j+1])){
			temp += datab[++j];
			mintemp = min(mintemp, (long long)datab[j]);
		}
		else if(s+1 <= i){
			temp += datab[--i];
			mintemp = min(mintemp, (long long)datab[i]);
		}
		result = max(result, mintemp*temp);
		//printf("%d %d %d\n",i, j, result);
	}
	return result;
}

맨 처음에는 아래 code와 같은 방식으로 했더니 37% 시간초과가 뜨더군요.

	for(i = s; i <= e; i++){
		for(j = i + 1; j <= e; j++){
			mintemp = 1000000;
			temp = 0;
			for(k = i; k <= j; k++){
				temp += datab[k];
				mintemp = mintemp > datab[k] ? datab[k] : mintemp;
			}
			//printf("%d %d %d\n",i,j, mintemp * temp);
			result = result > temp*mintemp ? result : temp*mintemp;
		}

두번째로 시도한 code는 아래와 같습니다. 역시 시간초과를 토해냈습니다.

	for(i = s; i <= mid; i++){//이렇게 바꾸면 무조건 중간을 포함하는 것만 check함!! 이렇게해도 시간초과 뜨네 에잉 
		for(j = mid + 1; j <= e; j++){
			mintemp = 1000000;
			temp = 0;
			for(k = i; k <= j; k++){
				temp += datab[k];
				mintemp = mintemp > datab[k] ? datab[k] : mintemp;
			}
			//printf("%d %d %d\n",i,j, mintemp * temp);
			result = result > temp*mintemp ? result : temp*mintemp;
		}
	}

중요한 것은 교차하는 부분 배열에서 최대 값을 찾는 것입니다. 분할한 지점에서 오른쪽으로 증가할지 왼쪽으로 증가할지를 어떻게 선택할건지 정하는 logic이 가장 핵심입니다.

 

몇 개의 test case를 아래에 두겠습니다. 도움이 되시길 바랍니다.

7
1 1 1 1 1 1 9
>>81

4
6 1 1 6
>> 36


4
2 5 1 3
>> 25

3
0 1 0
>> 1

2
1 3
>> 9