[C++/PGS] Lv.3 : 연속 펄스 부분 수열의 합 (DP)

 

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

프로그래머스

---

프로그래머스 레벨 3.

cpp 배열 선언도 까먹어버려서 .. 큰일났다 ㅋㅋ다시 다 공부해야지

 

이 문제는 dp로 풀어야하는데, 아이디어 떠올리기기ㅏ 조금 힘들었다

펄스 배열과 연속 부분수열을 보고 sliding window로 풀어야하나? 싶었는데

풀다 보니 left를 옮길 조건이 없어서 이게 아닌가보다 싶었다.

그래서 DP로 최댓값을 저장하면서 풀었다!

 

일차원 배열을 두개 쓰려다가, 더 효율적인 코드를 위해 이차원 배열로 바꾸었다.

dp[][0] -> 펄스가 1부터 시작

dp[][1] -> 펄스가 -1부터 시작

 

항상 최댓값을 고려할 때, 현재 원소 자신이 최대일 경우까지 고려할 것!!

 

 

나의 풀이

#include <string>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

long long solution(vector<int> sequence) {
    long long answer = 0;
    // dp? 윈도우? -> 윈도우는 고정 길이 탐색에 적합. dp로 풀어야함
    long long dp[500001][2] = {0,}; // i번째 인덱스까지의 최대 합
    int nowPulse = 1;
    dp[0][0] = sequence[0];
    dp[0][1] = sequence[0] * -1;
    answer = max(dp[0][0], dp[0][1]);
    for(int i=1; i<sequence.size(); ++i){
        nowPulse *= (-1);
        long long now = sequence[i]*nowPulse;
        dp[i][0] = max(dp[i-1][0] + now, now);
        dp[i][1] = max(dp[i-1][1] - now, (-1) * now);
        if(answer < dp[i][0]) answer = dp[i][0];
        if(answer < dp[i][1]) answer = dp[i][1];
    }
    return answer;
}