[programmers] 연속 펄스 부분 수열의 합

https://school.programmers.co.kr/learn/courses/30/lessons/161988

프로그래머스

 

 

------------------------------------------핵심 알고리즘-------------------------------------------

 

알고리즘은 간단하게 dp로 풀리며,

   dp[i] = max(seq[i], seq[i]+dp[i-1])

이다. O(n)의 탐색 속도를 보여준다.

 

들었던 의문은 왜 seq[i]가 항상 더해져야하는가 였는데,

다른 블로그의 글들을 참고하며 이해할 수 있었다.

 

여기서의 핵심은 연속되어야 하므로 이전까지에서 끊기는 경우를 dp로 담을 수 없다는 것이다.

즉, dp[i]는 반드시 현재 값(seq[i])를 포함한다.

따라서, dp[i] = max(현재값, 이전꺼의 최대+현재값)이 되어야 하는 것이다.

 

---------------------------------------문제 풀이---------------------------------------------------

 

sequence에 [-1,1,-1,1,...]을 곱한 수열이나 [1,-1,1,-1,...]을 곱한 수열에서 최대를 찾으면 되므로,

위에서 설명한 dp 식을 이용해 각 수열에서 모두 최대를 찾아주면 된다.

#include <string>
#include <vector>

using namespace std;

vector<int> seq1, seq2;

// 최대 연속 부분수열의 합.
// dp[i] = max(psum, 0) + seq[i]
// 여기서의 핵심은 연속되어야 하므로 이전까지에서 끊기는 경우를 dp로 담을 수 없다는 것이다. 즉, dp[i]는 반드시 현재 값(seq[i])를 포함한다.
// 그렇다면 dp[i] = max(현재값, 이전꺼의 최대+현재값)이 될 것이다.
// 자신만 포함하거나, 이전부터 일부를 포함하거나!
// 따라서, dp[i] = max(seq[i], seq[i]+dp[i-1])이 된다.
long long solution(vector<int> sequence) {
    long long answer = 0;
    seq1 = sequence; seq2 = sequence;
    // seq1 변경 (1,-1,1,-1,...), seq2 변경(-1,1,-1,1,...)
    int p = -1;
    for(int i = 0; i < seq1.size(); i++){
        if(i % 2 == 0){
            seq2[i] *= -1;
        }
        else{
            seq1[i] *= -1;
        }
    }
    // dp => O(N) 가능
    long long ret = 0;
    long long psum = 0;
    for (int i = 0; i < seq1.size(); i++)
    {
        // 왼쪽부터 i번째까지 더한 값 중 최대값 psum.
        psum = (psum > 0? psum : 0) + seq1[i];
        // 
        ret = psum > ret? psum : ret;
    }
    
    psum = 0;
    for (int i = 0; i < seq2.size(); i++)
    {
        // 왼쪽부터 i번째까지 더한 값 중에서 가장 큰 값 psum.
        psum = psum = (psum > 0? psum : 0) + seq2[i];
        // 
        ret = psum > ret? psum : ret;
    }
    
    answer = ret;
    
    return answer;
}

 

--------------------------------------------후기-------------------------------------------------

 

처음엔 투포인터를 떠올렸는데, 적용하는 법에 대해 생각해보다가 너무 오래 걸려 '최대 부분 수열의 합'을 검색해 풀었다.

 

dp를 너무 오랜만에 접하다보니, 뇌까지 굳은 느낌..

여러 유형을 꾸준히 푸는 연습을 해야겠다!