[백준/C++] 1912번 연속합

문제링크

1912번 연속합

 

수열에서 연속된 수들의 구간합을 더하면서 최대값을 찾는 문제

단순하게 브루트 포스 방식으로 이중for문을 사용하면 답이 나오기는 하지만 시간초과가 발생함

동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있느냐를 물어보는 문제

동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것을 의미하며 알고리즘이 아니라 문제 해결 방식이다.

자세한 내용은 아래를 참고하면서 학습하는 게 좋다.

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

 

문제를 일반화 한다면

n번까지의 연속합의 최대 합은 [n-1번까지의 최대값 + n번값] 혹은 [n번값] 둘 중 큰 값이 된다.

이를 계속 비교해나가면서 최대값을 저장해두었다가 비교할 때 사용하고 결과로 출력하면 된다.

 

 

제출코드

#include <iostream>

using namespace std;

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

int N = 0, answer = 0;
// 수열이 들어갈 배열
int nums[100000];
// 부분 구간 합을 저장할 배열
int maxSum[100000];

int main()
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> nums[i];
	}

	// 정답 초기값 설정(+ 가장 첫 수가 제일 크고 나머지가 작은 경우도 처리 가능)
	answer = nums[0];

	for (int i = 0; i < N; i++)
	{
		// 일단 수열에 있는 현재 i가 가장 크다는 가정하에 값 삽입
		maxSum[i] = nums[i];
		if (i == 0) continue;
		// 만약 그것보다 이전까지의 수열이 가장 크다면 끊어줌(i번째에서 끝나는 제일 큰 연속합)
		if (maxSum[i] < maxSum[i - 1] + nums[i])
		{
			maxSum[i] = maxSum[i - 1] + nums[i];
		}
		// 현재까지 정답보다 크다면 최대값을 바꿔줌
		if (maxSum[i] > answer)
		{
			answer = maxSum[i];
		}
	}

	cout << answer;

	return 0;
}