[DP] BOJ 1912 번 문제풀이

문제분석

처음에 해석 잘하셔야 돼요!!...

 

저는 이해를 잘 못해서 연속된 

두 개의 수로 풀고 기차게 틀렸었습니다...

 

그러니까 이 문제는 연속된 여러 개의 숫자를 더했을 때

나올 수 있는 가장 큰 수를 찾는 문제죠.

 

만약에 이 문제가 DP 문제인 것을 파악하지 못했다면

3중 for문으로 해결할 수도 있어요.

시작점, 끝점, 중단점 이런 식으로 나눠서요.

	cin >> n;
	for (int st = 1; st <= n; st++)
	{
		for (int end = st; end <= n; end++)
		{
			int tot = 0;
			for (int stop = st; stop <= end; stop++) tot += s[stop];
			mx = max(mx, tot);
		}
	}

하지만!

이러면 이미 이전에 구했던 최댓값들을

반복적으로 구하게 되는 과정이 생깁니다.

 

이런 과정을 생략하는 방법이 바로

메모이제이션을 이용한 DP 죠?

 

자, 이 문제의 점화식을 도출해 봅시다.

D[i] = i 번째 항을 마지막으로 하는 수열의 최대합

이라고 합시다.

 

그러면

D[i] = max( D[i -1] , 0) + S[i]

라는 점화식이 도출됩니다.

 

i 번째까지 수열의 최대합이 양수일 때만

더한다는 의미입니다.

 

코드

 

#include "bits/stdc++.h"

using namespace std;
int d[100005];
int s[100005];


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> s[i];
	}
	d[1] = s[1];

	for (int i = 2; i <= n; i++)
	{
		d[i] = max(d[i - 1], 0) + s[i];
	}


	cout << *max_element(d + 1, d + 1 + n);
}