알고리즘 :: 백준 :: DP :: 13398:: 연속합 2

문제

문제링크

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

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

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

문제접근

• 숫자 하나를 제거할 수 있다는 조건이 정말 까다롭다.
• 연속합 1 문제에서 우리는 $O(n)$으로 연속합을 구할 수 있음을 구현했다. (https://velog.io/@embeddedjune/알고리즘-백준-DP-1912-연속합)
• k번째 수를 제거하고 $O(n)$으로 연속합을 구하는 것은 좋은 방법이지만, n개에 대해 반복 수행하면 $O(n^2)$ 알고리즘이 되기 때문에 한 번 구한 연속합을 dp배열에 저장한 뒤 사용하는 전략을 사용하자.
• k번째 수를 제거한다는 것은, k-1번째 수까지의 연속합과 k+1번째부터의 연속합을 더하는 것으로 표현할 수 있다.
• 따라서 $O(n)$으로 정방향 연속합을 1회 구하고, 역방향 연속합을 1회 구한 뒤 각각을 따로 저장하자.
• 제거해야하는 수는 음수라는 점을 사용해서 값을 입력받을 때 음수의 위치를 파악해둔 뒤 연산 횟수를 효율적으로 줄여보자.
• 이 문제의 교훈은 때로는 DP는 배열을 2개를 만들어서 해결해야한다는 점이다. 다음에는 바이토닉 LIS에서 이 방법을 적용해보자.

다른 풀이

• 이번에도 똑같이 dp 배열을 2개 사용하지만 의미를 조금 다르게 부여해보자.
• dpL[i]는 이전 풀이와 똑같이 i번째 숫자를 마지막으로 하는 연속합을 저장한다.
• dpR[i]는 i번째 숫자를 제거하는 게 더 낫다고 판단되는 경우 제거한 연속합을 저장한다.
  • dpR[1]이 10인 이유는 dpR[0] + a[1] 보다 dpL[0]이 더 크기 때문에 삭제하는 것이 더 낫다고 판단한 결과이다.
  • 그렇게 -4를 제거한 경우에 대해 주욱 연속합이 저장되다가 -35를 만났을 때 dpR[6] + a[7] 보다 dpL[6]이 더 크기 때문에 삭제하는 것이 더 낫다고 판단한다.
  • 숫자는 하나만 제거할 수 있기 때문에 -35를 제거했다면 -4를 제거한 경우에 끌고왔던 연속합은 무의미해진다. 하지만 dpL[] 배열에 i번째까지의 연속합이 저장돼있기 때문에 해당 값을 가져와 덮어씌운다.
  • 즉, 이제 -4는 제거하지 않고 -35를 제거한 경우의 연속합을 계산해나간다.
    
• 설명만 들으면 dpR[]의 가장 큰 값이 답이라고 생각하겠지만, 만일 a[i]가 0이고 dpR[i - 1]이 음수라면 오히려 큰 값은 dpL[]에 저장되게 된다. 따라서 그 경우까지 고려해줘야 한다.

코드

#include <iostream>
#define SIZE 100000
using namespace std;

int n, a[SIZE], dpL[SIZE], dpR[SIZE], neg[SIZE];
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	
    	// 음수의 개수, 전체 원소의 합 그리고 가장 큰 수를 구한다.
	int cnt = 0, sum = 0, highest = -1001;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		sum += a[i];
		highest = max(highest, a[i]);
		if (a[i] < 0) neg[cnt++] = i;
	}
    	// [예외처리] 원소 1개인 경우, 음수가 없는 경우
	if (n == 1 || cnt == 0) { cout << sum << '\n'; return 0; }
	// i번째 수를 끝으로 하는 연속합을 계산한다. 
	dpL[0] = a[0];
	for (int i = 1; i < n; ++i)	dpL[i] = max(dpL[i - 1] + a[i], a[i]);
	// i번째 수에서 시작하는 연속합을 계산한다.
	dpR[n - 1] = a[n - 1];
	for (int i = n - 2; i >= 0; --i) dpR[i] = max(dpR[i + 1] + a[i], a[i]);
	// neg[i]번째에 있는 음수를 제거한다.
    	// neg[i]-1 번째까지의 연속합 + neg[i]+1번부터의 연속합
	int ans = highest;
	for (int i = 0; i < cnt; ++i) {
    		// neg[i]가 0인 경우, n-1인 경우 예외처리 해줬다.
		if (neg[i] - 1 < 0) ans = max(ans, dpR[neg[i] + 1]);
		else if (neg[i] + 1 >= n) ans = max(ans, dpL[neg[i] - 1]);
		else ans = max(ans, dpL[neg[i] - 1] + dpR[neg[i] + 1]);
	}	
	cout << ans << '\n';
}

다른 풀이

#include <iostream>
using namespace std;
int N, a[100000], dpL[100000], dpR[100000];
int solve() {
	if (N == 1) return a[0];
	dpL[0] = a[0], dpR[0] = a[0];
	for (int i = 1; i < N; ++i) {
		dpL[i] = (a[i] < dpL[i - 1] + a[i]) ? dpL[i - 1] + a[i] : a[i];
		dpR[i] = max(dpL[i - 1], dpR[i - 1] + a[i]);
	}
	int ret = -1001;
	for (int i = 0; i < N; ++i) ret = max(ret, max(dpL[i], dpR[i]));
	return ret;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> a[i];
	cout << solve() << '\n';
}

결과