백준 1912 연속합

문제

문제링크: https://www.acmicpc.net/problem/1912

풀이전략

1. 이 문제는 완전탐색으로 해결하려고 할 경우 시간복잡도가 O(n^2)이 나오기 때문에 1초라는 시간제한을 맞출 수 없다. 따라서 O(n)으로 끝내는 법을 찾아야한다.
2. 값을 순차적으로 더하여 나가지만 새로운 값을 더한 값이랑 지금까지의 현재 값중 더 큰값으로 바꿔주는 알고리즘을 사용한다.
3. DP를 꼭 재귀적으로 해결할 필요는 없다. 반복문으로 사용 가능하다.

코드

#include<bits/stdc++.h>

using namespace std;

#define mine

int N;
int a[100001];
int dp[100001];
int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    for(int i=1; i<=N; i++){
        cin >> a[i];
    }
    memset(dp, 0, sizeof(dp));
    int res = -987654321;
    for(int i=1; i<=N; i++){
    	// 핵심부분이다.
        // 계속 더해주되, 현재 값과 지금까지의 값중 더한 것 중에 더 큰것을 dp에 저장시켜준다.
        // 이 방법 기억해두도록 하자
        dp[i] = max(dp[i-1]+a[i], a[i]);
        res = max(dp[i], res);
    }
    cout<<res<<endl;

    return 0;
}

소감

지금까지 단순히 DP문제들은 대부분 재귀로 해결하려고하였지만, 이렇게 반복문으로 손쉽게 사용할 수 있다는 것을 배웠다. 또한 연속합 문제는 이런식으로 풀어야겠다는 풀이과정을 잘 복습해야겠다.