[백준/BOJ] 백준 1912번 : 연속합

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

1912번: 연속합

point지점에서 시작하는 연속된 수들의 최댓값을 구하는 함수를 만들고, point지점이 0~n-1일 때를 모두 확인해 그중 가장 큰 값을 구한다. cache를 만들어서 한번 계산한 값은 다시 계산하지 않도록 하여 시간을 단축했는데, 주의해야 할 점은 cache를 습관처럼 -1로 초기화하면 안 된다는 점이다. 왜냐하면 solve()의 계산 결과로 -1이 나올 수 있기 때문이다. 이 코드에서는 cache를 solve()를 통해 나올 수 없는 987654321로 초기화하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int cache[100000];
vector<int> input;

void makeCache()
{
	//solve()의 결과로 나올수 없는 값으로 cache를 초기화 한다
	for (int i = 0; i < 100000; i++)
		cache[i] = 987654321;
}

//point지점에서 시작하는 연속된 수들의 최대값을 구한다
int solve(int point)
{
	int& ret = cache[point];

	//cache[point]가 987654321이 아니라면 이전에 계산했던 값이다
	if (ret != 987654321)
		return ret;

	//기저 사례(수열의 끝에 도달한 경우)
	if (point == n - 1)
	{
		ret = input[n - 1];
		return ret;
	}

	//point 지점값과 point 지점값 + point 다음 지점에서 시작하는 연속된 수들의 합의 최대값 중 큰 값이 point지점에서 시작하는 연속된 수들의 합의 최대값이다.
	ret = max(input[point], input[point] + solve(point + 1));

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	//cache를 초기화 한다
	makeCache();

	int temp;
	int result = -987654321; //result를 매우 작은 값으로 초기화

	cin >> n;

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

	for (int i = 0; i < n; i++)
	{
		//연속된 수가 i번째에서 시작하는 경우중 가장 큰 값을 구한다
		result = max(result, solve(i));
	}

	cout << result;

	return 0;
}