BOJ - 연속합 (1912번) C++

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

1912번: 연속합

dp 문제입니다. 실력이 늘어가는 것 같아 기쁘네요~

 

문제 요약 : 수열이 주어지는데, 수열의 수 중, 연속적으로 수를 골랐을 때 나올 수 있는 최댓값을 구해라.

 

우선, 연속적이라는 말에 주목했습니다.

수열에서 연속적인 수라는 건 어떤 수의 좌, 우에 있는 수를 뜻한다고 생각할 수 있겠죠?

 

그러니까 연속적이면, 부분적으로 구하지 않아도 된다는 뜻으로 저는 받아들였습니다.

=> 반복문 하나로 쭉 구하면 되겠구나~

 

그리고 dp 라는 배열을 만들어 주었습니다. 이때 dp[a] = b의 의미는

"길이가 a인 연속적인 수열에서의 최댓값은 b이다."

라는 의미로 사용했습니다.

 

그러면 이제 예를 들어서 점화식을 구해봅시다.

A = {1 , 3 , -4, 5}라고 합시다.

처음에 dp 배열을 입력 값으로 초기화 해주었습니다. 

왜냐하면 수열의 각 항은 자기 자신을 최댓값으로 가질 수 있으니까요.

문제에서 한 개 이상을 선택하라고 나와있으니 문제될 것은 없습니다.

item 이라는 입력 값을 받을 배열을 선언해주고 아래와 같이 초기화 해줬습니다.

	int n, res;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> item[i];
		dp[i] = item[i]; //수열의 각 항은 자기 자신을 최댓값으로 가질 수 있다.
	}
	res = item[1];

그리고 결과 값을 저장할 변수인 res를 생성했습니다.

res 또한 item[1]로 초기화 해주었습니다.

 

자, 이제 위의 예시를 토대로 구해봅시다.

dp[1]은 구했고... 현재 최댓값(res)은 1 입니다.

dp[2]는? 

연속적으로 구하니까

1) 자기 자신만 선택한 값 => dp[i] 

2) 자기 이전의 값에 자신의 값을 더한 값 => dp[i -1] + item[i]

이 두 가지만 따지면 됩니다.

그러니까 2) 에 의해 최댓값은 4가 됩니다. 그리고 res 또한,

크기를 비교해서 갱신 해줍니다.

 

그리고 dp[3]은?

2)의 값이 더 크니까 0입니다. 

근데 최댓값 갱신은 못하죠. 4보다 작으니까요.

 

dp[4]는? 1) 2) 가 같으니 5이고 res 또한 갱신해서 5네요.

따라서 5입니다.

 

전체 소스코드는 아래와 같습니다.

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <deque>

#define MIN 2147483647;
#define MAX 0; 

using namespace std;
typedef unsigned long long int ll;
int item[100001];
int dp[100001]; // dp[a] = b : 연속된 길이가 a인 수열에서의 최댓값은 b이다
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, res;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> item[i];
		dp[i] = item[i]; //수열의 각 항은 자기 자신을 최댓값으로 가질 수 있다.
	}
	res = item[1];
	for (int i = 2; i <= n; i++)
	{
		dp[i] = max(dp[i], dp[i - 1] + item[i]);
		res = max(res, dp[i]);
	}
	cout << res;
}

분명 혼자 생각해서 풀었는데 설명이 쉽지가 않네요.. 명확하게 설명하기 참 어렵습니다.