[백준] 연속합_1912

기초 dp 문제들 중에 안 푼게 꽤 있길래 다시 풀고 있다... 히히..

숫자는 어차피 연속적으로 더해야 하므로 바로 전 숫자만 고려하면 된다. 

cache[i] = max(arr[i], arr[i] + cache[i - 1]);

지금 내 숫자(arr[i])에 그 전까지 연속적으로 더해왔던 숫자 합(cache[i-1]을 더해서 손해가 난다면 이 합을 더할 필요가 없다. 연속을 끊고 cache에는 지금 숫자만 저장하면 된다. 

 

**몰랐던 것  

잘 가다가 틀려서 왜 틀렸을까 생각해봤는데 

최댓값을 업데이트하는 for문 부분을 i=1 인덱스에서부터 시작하게 했기 때문에, 숫자가 하나만 들어오는 경우에는 최댓값을 업데이트하지 못해 틀린 것이었다. 

그래서 숫자가 1개인 경우에는 그 숫자가 최댓값이 되도록 설정하고, 나머지 경우에는 ans = -0x7FFFFFFF; 로 초기 최솟값을 설정했다. 그리고 또 틀렸다. 

생각해보니 이런 문제는 최솟값을 일부러 엄청 작게 잡을 필요가 없었다... 모든 수가 음수인 최악의 경우라도 숫자 하나만 더하면 되니 작아봤자 -1000이기 때문이다. 혹은 그냥 초기 숫자 하나를 최솟값으로 지정해도 된다.

 

앞으로 아무 생각없이 0x7FFFFFFF를 쓰지 말아야겠다ㅎㅎ

0x3f3f3f3f 이 값은 2배해도 int 범위를 안 벗어나면서 10억이 넘는다고 한다. 

 

#include <iostream>
using namespace std;
 
int N;
int arr[100000], cache[100000];
 
int max(int a, int b) { return a > b ? a : b; }
 
int main() {
    cin >> N; 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    cache[0] = arr[0];
    int ans = arr[0];
    for (int i = 1; i < N; i++) {
        cache[i] = max(arr[i], arr[i] + cache[i - 1]);
        if (cache[i] > ans) ans = cache[i];
    }
    cout << ans << "\n";
    return 0;
}