[백준][C++][DP] 13398 연속합 2

13398번: 연속합 2

 

 

이 문제는 범위를 나누어서 생각해야 하는 문제이다. 

 

그렇기 때문에 top-down 방식보다 bottom-up 방식이 더 풀기 수월할 것 같은 문제이지만, 일단 나는 top-down 위주로 연습하고 있기 때문에 top-down으로 풀이하겠다. 

 

 

이 문제의 조건은 1912 연속합 문제와 거의 동일하지만 한 가지의 추가 조건이 있는데, 수열에서 수 하나를 뺄 수 있다는 조건이다.

 

이 추가 조건에 대한 고려로써 먼저 수열에서 수를 첫번째부터 마지막까지 하나씩 빼본 후 테스트하는 방법이 있을 수 있다. 

그러나 이런 풀이의 경우 연속합을 구하는 알고리즘의 시간복잡도 O(N)에 수를 하나씩 빼기 위한 시간복잡도 O(N)이 곱해져 O(N^2)의 시간복잡도가 된다. 따라서 시간 초과에 걸리게 된다. 

 

 

 

만약 우리가 선택할 연속합의 범위가 i번째 수를 포함하고 있고, 

i번째 수를 제외하는 경우를 생각해보자. 

(우리가 선택할 연속합의 범위가 제외할 수를 포함하지 않는 경우엔 수를 제외하는 행위가 결과에 영향을 미치지 않을 것이다. 따라서 우리는 연속합 범위에 있는 수를 제거하는 경우를 고려한다.)

 

이 경우 우리가 선택할 연속합의 범위는 다음과 같이 표현할 수 있다.

a[j] ~ a[i-1] / a[i+1] ~ a[k] (0 < j <= i-1, n >= k >= i+1의 임의의 수)

 

즉 i-1번째 요소로 끝나는 연속합 / i+1번째 요소로 시작하는 연속합 

이렇게 두가지의 연속합으로 범위를 분리할 수 있다. 

 

 

따라서 이 두 범위의 연속합을 더해주면 우리가 구하고자 하는 i번째 수를 뺏을 때의 연속합이 되고, 모든 i에 대해 max값을 구해주면 되는 문제이다. 

 

 

추가적으로 주의해야 할 점은 원소를 제거하지 않는 경우도 고려해줘야 한다는 점과, 

원소는 무조건 1개 이상 선택해야 한다는 점이다.

 

 

#include <iostream>

int d[100'001]; //d[n] = n번째 요소로 끝나는 연속합의 최대값
int dr[100'001]; //dr[n] = n번째 요소로 시작하는 연속합의 최대값
int a[100'001]; //수열 저장

int dp(int n)
{
	if (n <= 0) return 0;
	if (d[n] != 0) return d[n];

	d[n] = a[n];
	if (d[n] < dp(n - 1) + a[n]) d[n] = dp(n - 1) + a[n];

	return d[n];
}

int dpr(int n, int max)
{
	if (n == max) return a[max];
	if (n > max) return 0;
	if (n < 1) return 0;

	if (dr[n] != 0) return dr[n];

	dr[n] = a[n];
	if (dpr(n + 1, max) + a[n] > dr[n]) dr[n] = dpr(n + 1, max) + a[n];

	return dr[n];
}

int main()
{
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; ++i)
		std::cin >> a[i];

	int result = dp(1);
	for (int i = 2; i <= n; ++i) //수를 제거하지 않는 경우의 최대값
	{
		if (result < dp(i)) result = dp(i);
	}

	for (int i = 1; i < n; ++i) //i번째 수를 제거하는 경우
	{
		if (result < dp(i - 1) + dpr(i + 1, n))
			result = dp(i - 1) + dpr(i + 1, n);
	}
	std::cout << result;
}

 

 

사실 어떻게 풀긴 했지만 코드가 좀 마음에 안든다..

bottom-up 방식도 연습해야 할 듯