프로그래머스[Lv.3] - 연속 펄스 부분 수열의 합

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 

펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …]과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.

예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 

또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.

정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해 주세요.

https://school.programmers.co.kr/learn/courses/30/lessons/161988?language=cpp 

프로그래머스

---

 

 

 

 

 

 

제한 사항

• 1 ≤ sequence의 길이 ≤ 500,000
• -100,000 ≤ sequence의 원소 ≤ 100,000
  • sequence의 원소는 정수입니다.

---

 

 

 

 

 

 

풀이

메모이제이션(memoization)을 활용하면 간단하게 풀 수 있다.

기본적인 접근법은 vector의 각 요소가 부분 수열 중 가장 오른쪽에 포함됐을 때를 가정하며 진행한다.

그리고 그 결과를 vector의 기록하며 진행한다.

vector<long long> plus(sequence.size(), 0);   // 해당 요소가 +로 포함
vector<long long> minus(sequence.size(), 0);  // 해당 요소가 -로 포함

첫 요소는 이전 요소의 결과가 없으므로 곧바로 기록한다.

plus[0] = sequence[0];
minus[0] = sequence[0] * -1;

answer = max(plus[0], answer);
answer = max(minus[0], answer);

이때, 첫 요소만 포함하는 부분 수열이 가장 큰 결과가 될 수 있으므로 answer도 계산한다.

 

 

현재의 요소가 -의 펄스 수열과 곱해질 수도 있고 +의 펄스 수열과도 곱해질 수 있다.

만약, 현재 요소가 +로 부분 수열에 포함이 된다면 이전 요소는 -로 포함되었을 것이다.

반대로 현재 요소가 -로 부분 수열에 포함이 된다면 이전 요소는 +로 포함되었을 것이다.

따라서, plus와 minus를 교차하며 계산한다.

// sequence[i]가 +,-로 포함 될때를 각각 계산
plus[i] = max(minus[i-1] + sequence[i], (long long)sequence[i]);
minus[i] = max(plus[i-1] + sequence[i] * -1, (long long)sequence[i] * -1);

 

그리고 결과들을 answer와 비교하며 최댓값을 갱신한다.

answer = max(plus[i], answer);
answer = max(minus[i], answer);

 

 

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

long long solution(vector<int> sequence) {
    long long answer = 0;
    
    vector<long long> plus(sequence.size(), 0);
    vector<long long> minus(sequence.size(), 0);

    plus[0] = sequence[0];
    minus[0] = sequence[0] * -1;
    
    answer = max(plus[0], answer);
    answer = max(minus[0], answer);
    
    for(int i = 1; i < sequence.size(); i++)
    {
        // sequence[i]가 +,-로 포함 될때를 각각 계산
        plus[i] = max(minus[i-1] + sequence[i], (long long)sequence[i]);
        minus[i] = max(plus[i-1] + sequence[i] * -1, (long long)sequence[i] * -1);
        
        answer = max(plus[i], answer);
        answer = max(minus[i], answer);
    }
    
    return answer;
}

---