[백준] 1912번 : 연속합

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 연속된 수들의 합을 갱신하는 dp1과, 현재 수까지의 수열 중 연속된 수들의 합의 최대값을 갱신하는 dp2, 총 두 개의 dp를 Bottom-Up 방식으로 갱신하여 풀었다.

1) 벡터 nums를 선언해 주어진 수열을 입력받아 저장한다.

2) 1차원 배열 dp와 maxValue를 선언하고, dp[1]과 maxValue[1]을 nums[1]으로 초기화한다.

• dp[i] : i번째 수까지의 연속된 수들의 합, 합이 음수가 되면 그 다음 수부터 다시 시작
• maxValue[i] : i번째 수까지의 수열 중 연속된 수들의 합의 최대값
• 첫 번째 수까지의 수열일 때는 하나의 수밖에 없으므로 두 경우 모두 첫 번째 수 자체가 된다.

3) i가 2 ~ n일 때까지 경우의 수를 전부 갱신한다.

• 일단 현재 수까지 연속된 수들의 합 = 직전 수까지의 연속된 수들의 합 + 현재 수
• 직전 수까지 연속된 수들의 합이 음수라면 현재 수에 더하면 손해이므로 현재 수부터 다시 시작
  • 이를 점화식으로 표현하면 (i : 현재 순서 인덱스)
    • if(dp[i - 1] > 0) dp[i] = dp[i - 1] + nums[i]
    • else dp[i] = nums[i];
• 이후 maxValue에 현재 수까지의 연속합 중 최대값을 갱신해준다.
  • 직전 수까지의 maxValue와 현재 수까지의 dp를 비교해서 더 큰 값이 maxValue에 저장된다.
  • 이를 점화식으로 표현하면 (i : 현재 순서 인덱스)
    • maxValue[i] = max(maxValue[i - 1], dp[i])

4) maxValue[n]에 n까지의 수열 중 최대합이 저장되므로 해당 수를 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
int dp[100001];			// 연속된 수들의 합이 저장된다. 단, 합이 음수가 됐을 때는 그 다음 수부터 다시 시작한다.
int maxValue[100001];	// maxValue[i] : i 번째 수까지의 수열 중 연속된 수들의 합의 최대값
vector<int> nums;

void solution()
{
	dp[1] = nums[1];
	maxValue[1] = nums[1];
		
	for (int i = 2; i <= n; i++)
	{
		if (dp[i - 1] > 0)					// 현재 순서까지 연속된 수들의 합 = 직전 수까지의 합 + 현재 수
			dp[i] = dp[i - 1] + nums[i];
		else								// 직전 수까지의 합이 음수가 되었으면 더하면 손해이므로 현재 수부터 다시 시작
			dp[i] = nums[i];

		maxValue[i] = max(maxValue[i - 1], dp[i]);		// 직전 수까지의 최대합과 현재 순서까지 연속합을 비교했을 때 더 큰 값을 현재 수까지의 최대합으로 갱신
	}
	cout << maxValue[n];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	nums.push_back(0);
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		nums.push_back(num);
	}
	solution();
}