연속합 (feat. 백준, 1912번)

연속합
https://www.acmicpc.net/problem/1912

1912번: 연속합

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1912
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, arr[100001], dp[100001];
	cin >> N;
	for (register int n = 1; n <= N; ++n)
		cin >> arr[n], dp[n] = arr[n];
	for (register int i = 1, j; i < N; ++i) {
		for (j = i + 1; j <= N; ++j) {
			if (dp[j] < dp[j - 1] + arr[j])		dp[j] = dp[j - 1] + arr[j];
			else								break;
		}
	}
	cout << *max_element(dp + 1, dp + N + 1) << endl;
	return 0;
}
// *&)*@*

1. dp의 초기값은 입력받은 값을 기초로 합니다.
2. 배열의 두번째 항목부터 검사를 합니다. 이때 두번째 dp와 첫번째 dp + 두번째 arr를 비교하며, 만약 두번째 dp < 첫번째 dp + 두번째 arr인 경우만 다음 인덱스로 넘어갑니다. 왜냐면 조건이 만족하지 않다면, dp를 갱신할 이유가 없기 때문입니다.
3. 다음은 세번째 항목을 검사합니다. 이때 세번째 dp와 두번째 dp + 세번째 arr도 동일하게 비교하고 만약 위 부등호가 만족된다면 세번째 dp = 두번째 dp + 세번째 arr로 갱신합니다.
4. 즉 4개의 수열이라고 가정하면 1,2,3,4,1+2,1+2+3,1+2+3+4,2+3,2+3+4,3+4 의 경우중 가장 큰 값을 구하는 것입니다. 단, 1+2의 결과가 1+2+3보다 크다면 1+2+3+4를 계산할 의미가 없기 때문에 다음 2+3이 계산되도록 break가 존재합니다.