[DP] 백준 문제 풀이 - 1912 연속합

👩🏻‍💻 문제링크

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

 

1912번: 연속합

 

✍️ 아이디어

1. 문제 이해

• 연속해서 더할수 있는 수중에 가장 큰 수를 찾자

2. 점화식 D[ i ] = i번째 수로 끝나는 가장 큰 연속합

3. i번째 수열과 i-1번째 점화값과 i번째 수열을 더한 것중에 큰것을 저장한다

A[i] < A[i]+result[i-1] //A[i]는 수열 result는 값 저장 공간

 

✍️소스코드

• 이 아이디어는 강의 안봤으면 절대 안떠올랐을거 같다..(남의 코드는 내코드랑 비슷해서 패스~)

#include <iostream>
#include <algorithm>
using namespace std;
int result[100001];

int main()
{
	int A[100001];
	int n; cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>A[i];
	}
	result[1]=A[1];
	for(int i=2; i<=n; i++)
	{
		if(A[i]<A[i]+result[i-1])
		{
			result[i]=A[i]+result[i-1];
		}
		else{
			result[i]=A[i];
		}
	}
	cout<<*max_element(result+1, result+n+1)<<'\n';
}

 

 

체감난이도	걸린시간	참고	사용 문법
최상	1hour	강의 참고	Dp