[프로그래머스/C++] 연속 펄스 수열의 합

프로그래머스

 

• dp 문제
• 전체 수열에 펄스 수열을 곱해서 나올 수 있는 연속 펄스 수열의 종류는 두 가지 뿐
• 두 종류의 수열을 만든 후 두 수열을 돌면서 연속된 구간의 합이 최대가 되는 곳을 찾아야함
• 점화식이 2번째 요소부터 시작인데 sequence의 사이즈는 최소 1일 수 있어서 sequence의 사이즈가 1인 경우를 고려해야함

 

#include <string>
#include <vector>

using namespace std;

// 펄스 수열은 [1, -1, 1...] 또는 [-1, 1, -1...], 즉 1 또는 -1로 시작
// 전체 수열에 펄스를 곱해서 나올 수 있는 수열은 두 가지 뿐
// 두 종류의 수열을 만든 후 두 수열을 돌면서 연속된 구간의 합이 최대가 되는 곳을 찾아야함
// 점화식으로 나타내면 dp[i] = max(dp[i - 1] + sequence[i], sequence[i])

// dp가 2번째 요소부터 시작이다보니 주어진 수열의 사이즈가 1인 경우도 따로 고려해야함
// 이거 안해서 2번 테스트 케이스 틀림

// 연속 펄스 수열 만들기
vector<int> multiplyPurse(vector<int> sequence, int pulse) {
    for(int i = 0; i < sequence.size(); i++) {
        sequence[i] = sequence[i] * pulse;
        pulse *= -1;
    }
    
    return sequence;
}

long long solution(vector<int> sequence) {
    long long answer = INT32_MIN;
    int size = sequence.size();
    
    // 각각 1과 -1로 시작하는 펄스 수열을 곱한 연속 펄스 수열 만들기
    vector<int> sequence1 = multiplyPurse(sequence, 1);
    vector<int> sequence2 = multiplyPurse(sequence, -1);
    
    long long dp1[size];
    long long dp2[size];
    
    dp1[0] = sequence1[0];
    dp2[0] = sequence2[0];
    
    // 이거 안해줘서 틀림
    if(size == 1) {
        answer = max(dp1[0], dp2[0]);
        return answer;
    }
    
    // dp 수행
    for(int i = 1; i < size; i++) {
        dp1[i] = max(dp1[i-1] + (long long)sequence1[i], (long long)sequence1[i]);
        answer = max(dp1[i], answer);
    }
    
    for(int i = 1; i < size; i++) {
        dp2[i] = max(dp2[i-1] + (long long)sequence2[i], (long long)sequence2[i]);
        answer = max(dp2[i], answer);
    }
    
    return answer;
}