[BOJ] 1912: 연속합 (C++) with 누적합

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

1912번: 연속합

걸린 시간 : 39분 34초

---

이 문제는 어떤 알고리즘 유형인지 모르고 시작했다. 역시나 알고리즘 유형을 알아채는 게 제일 어렵다.

처음에 부분합과 투 포인터 알고리즘의 결합으로 시작했다가, 그냥 부분합으로 했다가, 다시 부분합과 투 포인터로 했다가 시간초과와 틀렸습니다가 떴다.... ㅠㅠ

 

결국 다 치워버리고 종이에 어떻게 해야할 지 차근차근 생각해보니 기본적인 다이나믹 프로그래밍으로 해결할 수 있었다. 요즘 코테들도 구현이랑 BFS만 주구장창 내다보니 다른 유형을 잘 생각 못하는 것 같다. 확실하게 정리할 필요가 있다.

 

다이나믹 프로그래밍이라는 건 일반항을 생각해야 한다는 것. sum[i] 를 "0번째부터 i번째 항까지 원소들 중에서 가장 큰 연속합" 으로 생각하면, sum[i] 는 2가지 후보 중 하나로 생각할 수 있다.

• sum[i-1] 과 arr[i] 항의 합, 즉 부분합이 계속 커진다면 계속 이어가는 느낌
• arr[i], 즉 자기자신. 전까지의 부분합들보다 지금 현재값이 더 커서 이전 값들을 없애버리는 느낌

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, mx = -987654321;
	int arr[100001];
	int sum[100001];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		sum[i] = max(arr[i], sum[i-1]+arr[i]);
		mx = max(mx, sum[i]);
	}
	cout << mx;
	return 0;
}