[C++] 백준 1912 연속합

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int result = -1001;
	vector<int> dp;

	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int temp;
		cin >> temp;
		dp.push_back(temp);
	}

	result = max(dp[0], result);

	for (int i = 1; i < n; i++)
	{
		dp[i] = max(dp[i - 1] + dp[i], dp[i]);

		result = max(dp[i], result);
	}

	cout << result;

	return 0;
}

 

풀이

1. 우선 결과 값을 쌓아가면서 먼저 계산을 해본다. dp적 사고를 통해 이전 값+현재값과 현재값을 비교를해준다.

2. max를 계속 업데이트하면서 가장 큰 값을 저장한다.

3. 현재 값보다 쌓아온 값이 더 작으면 갱신된다.

 

느낀점

아직도 dp적사고가 되지않는 것 같다. 좀 더 점화식을 세우는 것을 연습해야겠다.

 

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