<백준> 1912 연속합 / C++ 풀이

중점

1. 시간 제한 1초 라는 점.

2. 연속되는 수를 계속적으로 더해야 한다는 점. 이를 통해서 최종 답을 구한다.

3. 2번을 토대로 작은 부분의 문제의 해결이 전체의 답을 구한다는 것을 발견했다.

 

시간 제한이 있고 연속적으로 반복되는 작업을 수행한다는 점에서 DP 알고리즘을 사용해야 한다고 생각이 들었다. 따라서 배열을 선언하고 n번에는 n번째 까지의 입력받은 수들 중 연속하며 합이 최대인 경우를 저장한다. 만약 이전에 연속값을 더한것 보다 n번째 입력받은 값이 크다면 입력값을 저장한다. 매 순간 마다 두개를 비교하여 그때의 최종 값이 저장되게 한다. 이때 total_max라는 값을 선언하여 매순간 비교하여 연속되는 최댓값을 저장하게 한다.

 

---

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int d[100002];
int total[100002];
int n;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++){
        cin >> d[i];
    }

    total[1] = d[1];
    int total_max = total[1];

    for (int i = 2; i <= n; i++){
        total[i] = max(total[i - 1] + d[i], d[i]);
        if (total_max < total[i]) total_max = total[i];
    }

    cout << total_max;
}

 

처음에는 total[n]의 값이 가장 최대값이라고 생각했다. 하지만 연속되는 숫자를 더하는 것이므로 항상 max값을 비교해야 된다는 생각을 하지 못하였다.

 

질문은 댓글로 부탁드립니다. 감사합니다!