백준 #1912. 연속합
정리
-
이 문제도 다이나믹 프로그래밍 기법으로 해결할 수 있는 문제이다.
-
bottom-up 방식으로, 연속합의 최댓값을 비교해서 저장해 두고, 계속 수열을 비교해 나가면서 기존의 연속합의 최댓값과, 새로운 연속합의 값을 비교해 나가는 방식으로 문제를 해결했다.
-
수열의 숫자는 -1000보다 크거나 같고, 1000보다 같거나 작은 정수이다. 즉, 수열에 음수가 포함될 수 있다. 따라서 각 숫자가 양수인지 음수인지에 따라서 다르게 처리해줘야 한다. 자세한 내용은 아래 코드에 주석으로 적어 뒀으니 참고하면 좋을 듯하다.
정답 코드
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
int n;
int arr[100001];
int dp[100001];
// dp[]에는 각 인덱스에서의 연속합을 더해 갖고 있는 역할을 한다.
int res;
// res 변수에는 가장 큰 연속값을 저장해 두고, 최종적으로 답을 출력하는 역할을 한다.
cin>>n;
for(int i=1; i<=n; i++) {
cin>>arr[i];
}
if (arr[1] >= 0) dp[1] = arr[1];
else dp[1] = 0;
res = arr[1];
for(int i=2; i<=n; i++) {
if (arr[i] >= 0) {
// i번째 숫자가 양수인 경우, dp[]에 arr[i]를 더해준 것을 연속합으로 저장한다.
dp[i] = dp[i-1] + arr[i];
res = max(res, dp[i]);
}
else {
// i번째 숫자가 음수인 경우, 두 가지 case가 가능하다.
if (dp[i-1] + arr[i] >= 0) {
// 기존 연속합 + 이번 음수 >= 0일 경우, 그대로 더해 연속합으로 저장해 둔다.
dp[i] = dp[i-1] + arr[i];
res = max(res, dp[i]);
}
else {
// 기존 연속합 + 이번 음수 < 0일 경우, 이번 숫자를 더하면 연속합이 최대가 될 가능성은 없다.
dp[i] = 0;
res = max(res, arr[i]);
}
}
}
cout<<res<<endl;
return 0;
}
Author And Source
이 문제에 관하여(백준 #1912. 연속합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chnh506/백준-1912-연속합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)