[ 프로그래머스 C++ ] 연속 펄스 부분 수열의 합 - LV3

< 해설 >

누적 합이라는 개념을 처음으로 알고 적용시킨 문제이다.

먼저 누적 합을 설명하자면 다음 그림과 같다.

인덱스 2의 누적합은 인덱스 0 + 1 + 2 까지의 값이다. 식으로 표현하면

S(n) = S(0) + S(1) + ... S(n-1) + S(n)  이라고 하는데 그냥 전까지의 합이라고 생각하면된다. 모든 배열의 값이 특정 인덱스까지의 합이므로 S(n+1) = S(n-1) + arr[n] 을 하면 된다. (S(n)은 n까지의 누적합.)

특정 인덱스에 대한 값만 구하고 싶다면 S(n) - S(n-1) 을 해주면 된다.

 

다시 문제로 돌아와서 보면 펄스값에 따라 값이 양수/음수 로 바뀐다. 근데 어짜피 절대값은 바뀌지 않으므로 최대, 최소 값만 구해주면 된다. 펄스값은 1, -1, 1 ... 이든 -1, 1, -1 .. 이든 둘중 아무거나 일단 적용해준다.

 

그렇게 고정된 배열에 누적합을 계산하고 누적합에서의 최대값과 최소값을 구해준다.

여기서 생각해 주어야하는 반례가 있다. 누적합이 아닌 그냥 인덱스의 값이 제일 큰 경우이다. 그래서 max함수로 maxi에서 mini를 뺀 절대값과 maxi 자체의 값을 비교해서 더 큰 값을 리턴해주면된다.

 

< 문제 >

 

< 풀이 >

#include <string>
#include <vector>
#include "string.h"

using namespace std;

long long solution(vector<int> sequence) {
    
    // 펄스는 어짜피 -1, 1 or 1 -1 순서.
    // 하나 만들어서 abs 해준다.
    long long AddNum1[500001];
    memset(AddNum1, 0, sizeof(AddNum1));
    
    for(int i=0; i < sequence.size(); i++)
    {
        if(i % 2 == 0)
        {
            AddNum1[i+1] = AddNum1[i] + sequence[i] * (-1);
        }
        else
        {
            AddNum1[i+1] = AddNum1[i] + sequence[i];
        }
    }
    
    long long maxi=0;
    long long mini=0;
    
    for(int i=0; i< sequence.size(); i++)
    {
        if(AddNum1[i+1] < mini)
            mini = AddNum1[i+1];
        
        if(maxi < AddNum1[i+1])
            maxi = AddNum1[i+1];
    }
    
    return max(abs(maxi-mini), maxi);
}

코드 실행결과. 누적합을 사용해야만 풀 수 있는 케이스들만 모아둔것 같다. ㅋㅋ