[백준] 1912번 연속합 (C++) - 간단한 dp

1. 발상

dp[] 배열을 이용해 문제를 해결한다.

dp[i] = dp[i-1]+arr[i] 의 합과 arr[i] 중 큰 것

정답은 dp[i]에 저장된 값 중 최댓값

 

배열 정렬하기 귀찮아서 그냥 벡터 사용해서 값을 모두 insert한 뒤 sort 이용해 정렬했다. 

 

2. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
	cin.tie(NULL); ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int arr[n];
	int dp[n];
	
	for(int i=0; i<n; i++){
		cin >> arr[i];
	}
	
	vector <int> ans;

	dp[0] = arr[0];
	ans.push_back(dp[0]);
	
	for(int i=1; i<n; i++){
		int temp = 0;
		temp = max(dp[i-1]+arr[i], arr[i]);
		ans.push_back(temp);
		dp[i] = temp;
	}
	sort(ans.begin(), ans.end(), greater<int>());
	cout << ans[0];
}

전체 소스코드는 다음과 같다.

 

dp 이용 부분을 따로 놓고 보면 다음과 같다.

	for(int i=1; i<n; i++){
		int temp = 0;
		temp = max(dp[i-1]+arr[i], arr[i]);
		ans.push_back(temp);
		dp[i] = temp;
	}

dp[i] = max(dp[i-1]+arr[i], arr[i]);