백준 #1912 연속합

오늘은 DP문제를 하나 풀어보았다. 저번에 애를 먹었던 https://miffu-bh.tistory.com/7 이 문제와 풀다보니 비슷했다. 사실 공통점이라곤 뒤에서 부터 dp값 저장을 시작한 다는 것 말고는 없긴 하지만 이것을 예전에 풀어보지 않았다면 이 문제도 한참이 걸렸을 수도 있을 것 같다. 하지만 다행히 뒤에서부터 dp값을 변경해보면 되겠다는 생각을 빨리 할 수 있었고 쉽게 풀 수 있었다!

숫자들이 연속해서 들어오고, 연속한 수들만 더해 나갔을 때 가장 큰 값이 되는 것을 구하면 된다. 누가봐도 dp로 풀어야 함을 알 수 있어서 사실 나말고 다른사람들한테도 쉬웠을 것 같다ㅜ 그래도 이정도면 늘긴는거다!

처음부터 더해나가다 보면, 음수가 나왔을 때 이 음수를 더하고 계속 연속해 나가야 할지, 아니면 이 음수에서 멈추고 다음 수부터 처음부터 더해나가야 할 지 고민이 된다. 이를 해결하려면, 뒤에 나오는 수들을 다 확인해서 이후의 수들의 합 중 지금 확인하고 있는 음수보다 더 크게 되는 경우가 있는지를 확인해야 하는데, 그럼 저번 퇴사2 문제를 처음풀 때 겪었던 것처럼 시간 초과를 겪게 된다. 따라서 난 처음부터 확인하면 안되겠다는 것을 알게 되었고, 뒤에서부터 풀 생각을 하게 되었던 것 같다. 코딩도 경험이다!

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
//#include <numbers>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
int n;

vector<pair<int,int>> list;
int dp[100005];
int arr[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(int i=0; i<n;i++)
    {
        cin>>arr[i];
    }
    dp[n-1] = arr[n-1];
    int max_val = arr[n-1];
    for(int i= n-2; i>=0; i--)
    {
        if(dp[i+1] <0 )
        {
            dp[i]= arr[i];
        }
        else
        {
            if(arr[i] <0 )
            {
                if(dp[i+1] > arr[i])
                {
                    dp[i] = dp[i+1] + arr[i];
                }
            }
            else
            {
                dp[i] = arr[i] + dp[i+1];
            }
        }
        max_val = max(max_val, dp[i]);
    }

    cout<<max_val << '\n';
    return 0;
}

배열로 입력을 받고, 맨 뒤 원소의 dp값을 맨 뒤 원소의 값으로 지정해주고 n-2번째 부터 제일 첫번째 칸까지 차례로 탐색해왔다. 만약 한 칸 뒤의 dp[]의 값이 음수라면  현재 원소에서 더 뒤의 값들을 더해봤자 값이 더 작아지기만 하기 때문에 더해줄 필요 없이 자신의 원소 값을 dp값으로 해준다. 한 칸 뒤 dp값이 음수가 아니라면 이제 현재 원소값이 음수인지 아닌지를 판단해 주어야 한다.

 현재 원소 값이 0보다 만약 작다면 한칸 뒤의 dp 값이 현재 음수인 원소의 값보다 크다면 더해주는 것이 이득이다. 아닐경우 그냥 놔둔다.

현재 원소값이 음수가 아닐 때에는 한칸 뒤의 dp 값에 현재 원소를 더해준다. 각 원소에서의 dp를 구한뒤 max_val와 비교를 해 현재 최대값보다 더 큰 값이 있을 경우 그때 그때 바꿔준다.

 

이렇게 하면 1번의 for문안에 해결할 수 있다. 끝!