백준 1912번 C++

백준 1912번 연속합

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

1912번: 연속합

정답 코드

#include<iostream>
using namespace std;
int arr[100001];
int dp[100001];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int a;
	cin >> a;
	for (int x = 0; x < a; x++)
		cin >> arr[x];
	int max1 = -987654321;
	for (int x = 0; x < a; x++) {
		if (x == 0) {
			dp[x] = arr[0];
			if (dp[x] > max1)
				max1 = dp[x];
		}
		else {
			dp[x] = max(arr[x], dp[x - 1] + arr[x]);
			if (dp[x] > max1)
				max1 = dp[x];
		}
	}
	cout << max1;
}

문제 풀이

dp와 투 포인터 개념을 응용해서 풀 수 있는 문제입니다. 입력받을 배열과 dp배열 두 개를 만들어줍니다. 입력을 다 받은 후 max변수 초기값을 음수로 선언한 뒤
배열 크기만큼 for문을 돌립니다. 이때 x가 0이라면 arr[0]값을 넣어줍니다(x가 0이면 dp배열에 아무 값도 없기 때문). 그게 아니라면 dp[x]=dp[x-1]+arr[x]를 넣어줍니다. dp배열에는 최댓값이 들어가기 때문에 dp[x-1]과 arr[x]값을 더해주면 그 값이 최댓값이 되는지 그리고 배열 안에 원소들을 더해나갈 수 있습니다.