ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 1912 연속합 (C++)

Posted on Jul 14, 2021 #동적프로그래밍(DP)   #Algorithm  

1912 | 연속합

🙋‍♀️ 문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

🙌 입출력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

첫째 줄에 답을 출력한다.

🙋‍♂️ 예제 입출력

10
2 1 -4 3 4 -4 6 5 -5 1

14

5
-1 -2 -3 -4 -5

-1

🚀 코드

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

int n = 0;
vector<int> v;
vector<int> dp;

int main() {
	cin >> n;
	int x = 0;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	dp.push_back(v[0]);
	for (int i = 1; i < n; i++) {
		/*int sum = dp[i - 1] + v[i];
		if (n == 2) {
			sum = dp[i - 1];
		}
		if (sum >= 0) {
			dp.push_back(dp[i - 1] + v[i]);
		}
		else {
			dp.push_back(v[i]);
		}*/
		dp.push_back(max(v[i], dp[i - 1] + v[i]));
	}

	sort(dp.begin(), dp.end());
	cout << dp[n - 1];

	return 0;
}

🌠 메모

동적 프로그래밍 연습하려고 푼 문제. 계속 DP문제를 풀어서 그런지 생각보다 답이 금방 보였다.

연속된 몇 개의 수에 집중하면 생각해 봐야 할 포인트가 음수가 나오는 지점이라는 걸 알 수 있을 것이다. 계속 더해 나간 값을 dp 테이블에 저장할 텐데, 저장된 값이 음수이면 안더하면 된다. 즉, 앞에까지 더한 구간 버리고 지금부터 새로운 구간 합을 구한 다는 의미이다.

이후에는 dp테이블을 정렬해서 가장 큰 값을 출력했다. 왜냐하면 음수가 나오면 새롭게 구간합을 구하기 때문에 마지막 구간이 항상 크지 않기 때문이다.

풀기는 정말 금방풀었는데 틀렸습니다.를 보고 좀 슬펐다.😢 로직은 맞게 생각했는데 max를 통해서 현재 값고 더해진 값을 비교해야 한다. max(v[i], dp[i - 1] + v[i]) 정확한 반례는 못 찾았고, 이거저거 하다보니까 됐다. (조건문이니까 조건이 어설퍼서 어디 하나 삑사리 나간게 있을테지.. 질문 게시판의 반례는 전부 돌아가던데 뭐가 문제였을까?)

무튼 짜고 나서 보니까 코드를 심플하게 짜서 뿌듯했다. 🎈



# 카테고리