1912 연속합

연속합 (1912)

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이코드 (완전탐색)

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
// 1912 연속합

const int MAX = 100000;
int n;
vector<int> seq;

int max(int a, int b) {return a < b ? b : a;}
int sum(int a, int b) {
	int res = 0;
	while(a++ <= b) res += seq[a];
	return res;
}
int rowSum(int idx1, int idx2){
	// 기저 사례 : `
	return 0;
}

int main(){

	cin >> n;
	cin.ignore();

	for(int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		seq.push_back(tmp);
	}

	int maxSum = -1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= n; j++){
			maxSum = max(maxSum, sum(i, j));
		}
	}
	
	cout << maxSum << endl;
	
}

당연하게도 시간 초과가 나왔습니다. 100,000 * 100,000 이 1억이 훌쩍 넘는다는 것을 보고 당연히 예상했던 결과였습니다.

풀이코드 (메모이제이션)

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
// 1912 연속합

const int MAX = 100000;
int n;
int seq[MAX];
int cache[MAX];
int max(int a, int b) {return a < b ? b : a;}

// 해당 숫자로 끝났을 때의 최대 합을 저장하는 cache
int rowSum(int end){
	int& ret = cache[end];
	
	ret = max(cache[end - 1] + seq[end], seq[end]);
	
	return ret;
}

int main(){

	cin >> n;
	cin.ignore();

	for(int i = 0; i < n; i++)
		cin >> seq[i];

	int maxSum = seq[0];
	cache[0] = seq[0];
	
	for(int i = 1; i < n; i++){
		maxSum = max(maxSum, rowSum(i));
	}
	
	cout << maxSum << endl;
	
}

해설

---

적용한 레시피 / 방법론 + 접근법

1

최적화 문제 동적 계획법 레시피

1. 모든 답을 만들어보고 최적해를 반환하는 완전 탐색 알고리즘을 설계
2. 전체 답의 점수를 반환하는 것이 아닌, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제의 정의를 바꿈.
3. 재귀 호출의 입력에 이전의 선택에 관련된 정보는 꼭 필요한 것만 남기고 줄인다.
4. 입력이 배열이거나 문자열이라면 적절한 변환을 통해 메모이제이션 하도록 한다.
5. 메모이제이션 적용 

풀이

 

1. 완전 탐색 알고리즘 설계

2. 앞으로 남은 선택들에 해당하는 것만을 반환 하도록 하였습니다. 1912 번 문제에서는 해당 숫자로 끝날을 때의 최대 합을 저장하는 cache 를 설정하였습니다.

5. 바로 메모이제이션 적용

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

 

처음에 maxSum 을 생각없이 -1로 설정하여 오답이 나왔었습니다.

조금만 더 신경썼었더라면 maxSum 의 초기값은 입력의 첫번째 값이 되어야한다는 것을 알 수 있었을 것입니다.