백준 13398 - 연속합 2(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13398

13398번: 연속합 2

다이나믹 프로그래밍을 이용해 푸는 문제입니다.

연속된 수를 선택해 수열의 최댓값을 구하는 문제입니다.
이때, 수열의 수 중, 하나를 빼고 더할 수 있기에 점화식을 구해야했습니다.

저는 배열을 2차원 배열로 만들었습니다.
[X][2]로 만들어, [X][0]은 수를 하나도 빠짐없이 전부 더할 때, [X][1]은 수열 중, 하나를 빼고 더할 경우로 만들었습니다.

[X][0]에서 구할 수 있는 i번째 배열의 최댓값은 (지금까지의 모든 값의 합, 이전까지의 수를 버리고 현재만 가져올 때) 2가지를 비교하면 됩니다.
[X][1]에서 구할 수 있는 i번째 배열의 최댓값은 ([i-1][0]의 값, [i-1][1] + 현재 배열의 합) 2가지를 비교하면 됩니다.

이를 전부 구한 뒤, 구한 배열의 값을 전부 비교해 큰 값을 가져오면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#define INF 2100000000

using namespace std;

int N;
int arr[100001];
int dp[100001][2];
int maxi = -INF;

int Max(int x, int y, int z){
	x = max(x, y);
	x = max(x, z);
	return x;
}

void solve(){
	dp[1][0] = arr[1]; //해당 수를 선택했을 경우
	dp[1][1] = -INF;   //해당 수를 선택하지 않았을 경우
	for(int i = 2; i <= N; i++){
		dp[i][0] = max(dp[i-1][0] + arr[i], arr[i]);  //이전까지의 합 모두와 현재 자신만을 선택한 경우를 비교한다.
		dp[i][1] = max(dp[i-1][0], dp[i-1][1] + arr[i]);  //i-1까지 모두 선택했을때, i-1까지 1개뺴고 선택+현재 수를 비교한다.
	}
	for(int i = 1; i <= N; i++){
		maxi = Max(maxi, dp[i][0], dp[i][1]); // 지금까지의 모든 합을 비교한다.
	}
	cout << maxi;
}


int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++) cin >> arr[i];	solve();	
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.