프로그래머스 연속 펄스 부분 수열의 합(누적 합)

연속 펄스 부분 수열의 합 ←클릭

원래는 다르게 푸는 문제 같지만 쉽게 풀 수 있는 규칙을 찾았고, 다른 사람의 글을 참고하니 누적 합 방법인 것 같다.

변수 설정

p_s: pulse_sequence배열으로 원래 배열의 펄스 누적 합이다.

기본 개념

• p_s[0]에는 0을 삽입한다.
  
  
• p_s[i] = p_s[i-1] + sequence[i-1] * (-1)i-1의 점화식으로 p_s배열을 만든다
  
  
• p_s[i] = $\sum (-1)^isequence[i]$ 가 된다.
  
  
• p_s[j] - p_s[k] = sequence[k]부터 sequence[j-1]까지의 펄스 부분 수열의 합이다.
  
  
• p_s의 원소중 가장 큰 값과 가장 작은 값의 차를 구하면 연속 펄스 부분 수열의 합의 최대값이 된다.

코드

#define ll long long
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

long long solution(vector<int> sequence) {
    long long answer = 0;
    int sequence_len = sequence.size();
    vector<ll> p_s;
    p_s.push_back(0);
    for(int i = 1;i <= sequence_len;i++){
        p_s.push_back(p_s[i-1]+sequence[i-1]*pow(-1,i));
    }
    sort(p_s.begin(), p_s.end());
    
    answer = p_s[sequence_len]-p_s[0];
    return answer;
}

느낀점

운이 좋아 쉬운 규칙을 빨리 발견했지만 코딩테스트를 준비하는 입장에서 원래 문제의 의도대로 또한 풀어봐야 겠다. 또한 프로그래머스 환경에서 코딩테스트 연습을 시작해야겠다.

+추가)
dp를 사용한 풀이←클릭

정답~.~