프로그래머스 연속 펄스 부분 수열의 합 문제 풀이를 진행하였습니다.
문제 해석
문제를 읽으면 아래와 같은 해석이 가능합니다.
어떤 수열이 주어지며, 어떤 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다.
펄스 수열은 [1, -1, 1, -1...]또는 [-1, 1, -1, 1...]과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
연속 펄스 부분 수열의 합 중 최대값을 찾아야합니다.
문제 풀이
주어진 문제로 연속 수열이라는 점과 최대값을 구하는 점을 보고 누적합을 기록해나가며 문제를 풀어나가는 방식인 것을 알아내었습니다.
누적합을 기록하더라도 펄스 수열을 더해주어야 하기 때문에 많이 까다롭습니다.
우선 +로 시작하는 수열과 -로 시작하는 수열 두 가지를 배열로 만들어줍니다.
0번째 배열은 +배열이며 1번째 배열은 -배열이며 처음 값을 저장해준 후 비교합니다.
예를 들어 [2, 3, -6, 1]이라는 수열에서 최대값을 찾는다면
0~3번째 index까지 펄스 수열로 만들어 비교해보면 -8과 6이라는 값이 나오게 됩니다.
하지만 연속 부분 수열 중에서 구하는 것이기 때문에 주어진 수열의 최대값은 1~3번째 index를 더한 10이 답이 됩니다.
즉 수열을 시작하는 부분의 수 3보다 뒤에 존재하는 부분 수열이 더 작을 경우 뒤에 있는 수열을 버려도 된다는 뜻이 됩니다.
만약 [1, -3, 5, 12]라는 수열이 있다면 0~2번째 index까지 펄스 수열로 만들어 비교해보면 9와 -9라는 값이 나오게 됩니다.
이 둘 중 최대값은 9가 됩니다. 하지만 3번째 index가 12이기 때문에 뒤의 수열보다 3번째부터 새로 부분 수열을 만들어나가는 것이 최대값이 나오기에 3번째 index부터 새로 수열을 만들어나가면 됩니다.
전체 코드
#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;
long long solution(vector<int> sequence) {
long long answer = 0;
long long dp[2][500000];
dp[0][0] = sequence[0];
dp[1][0] = -sequence[0];
answer = max(dp[0][0], dp[1][0]);
for(int i = 1; i < sequence.size(); i++)
{
dp[0][i] = max((long long)sequence[i], dp[1][i-1] + sequence[i]);
dp[1][i] = max((long long)-sequence[i], dp[0][i-1] - sequence[i]);
answer = max(answer, dp[0][i]);
answer = max(answer, dp[1][i]);
}
return answer;
}출저
https://school.programmers.co.kr/learn/courses/30/lessons/161988
