오늘 풀어본 문제는 BOJ 1912 연속합 문제이다.
DP 문제를 푼지가 오래된 듯하여 열어봤는데 내 DP 기억 다 어디갔냐,,,
BOJ 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보다 작거나 같은 정수이다.
[출력]
첫째 줄에 답을 출력한다.
풀이
처음 생각해 낸 방법은 2개씩 더하고, 3개씩 더하고,, 하는 방법을 생각해보았지만 따져보니 O(N^2) 의 시간복잡도를 가지는 알고리즘 이었기 때문에 시간초과가 발생할 것 같았다.
혼자 고민 해 보았지만 잘 떠오르지 않았고 다른 풀이를 참고해야 했다.. 연습필요!
주어지는 숫자들의 합 중 최댓 값을 구해야 하는데 음수가 주어진다는 변수가 있다. 양수만 주어진다면 매우 간단한 일이겠지만 여기서는 음수가 주어지기 때문에 그 특징을 잘 다루어 주어야 했다.
주어진 예제 입력1 을 참고로 해 보자.
10개의 수가 다음과 같이 주어진다.
10 -4 3 1 5 6 -35 12 21 -1
-
index = 1
1번째 수까지의 최대 합은 당연히 그 수 자체인10이 될 것이다. -
index = 2
2번째 수-4를 보자.
2번째 수는 음수이기때문에 2번째 수까지의 최대합은6이어도 최대 연속 합은 여전히10이다. -
index = 3
3번째 수는3이다.
2번째 수 까지의 연속 합은6이고 3번째 수 까지의 최대 연속합은9이지만 이는10보다 작다. -
index = 7
7번째 수는-35이다. 같은과정을 거쳐오면서 6번째 수까지의 최대 연속 합은21이고 여기에 현재 수-35를 더하면-14이다. -
index = 8
8번째 수는12이다. 7번째 수까지의 합은-14인데 이를 채택해 현재 수 12를 더한 값-2보다 그냥 버리고 현재의 수를 택하는12가 더 큰 값을 가지므로 12번째 수 까지의 최대 합은12로 적어준다
즉, 직전 수 까지의 최대 합을 채택하는 것이 이득이면 택하고 그렇지 않다면 버리고 새롭게 현재 수 부터 연속합을 쌓아 나가는 방법이다.
구한 최대 합들을 배열 dp 에 적으면서 해당 값이 그동안 나왔던 값들 중 최대라면 결과를 갱신하여 O(N) 의 탐색이 끝나면 반환한다.
코드
#include <iostream>
#include <vector>
// boj 1912 연속 합, dp, 실버 2
using namespace std;
int getMaxSum(int N, vector<int> numbers){
int maxSum = numbers[0];
vector<int> dp(N, -1001);
dp[0] = numbers[0];
for (int i = 1; i <= N-1; ++i) {
dp[i] = max(numbers[i], dp[i-1]+numbers[i]);
if (dp[i]>maxSum) maxSum = dp[i];
}
return maxSum;
}
int main() {
int N;
cin>>N;
vector<int> numbers(N, 0);
for (int i = 0; i < N; ++i){
cin>>numbers[i];
}
cout<<getMaxSum(N, numbers);
return 0;
}