프로그래머스: 연속 펄스 부분 수열의 합⭐⭐⭐

체감 난이도 : ⭐⭐⭐
유형 : DP
걸린 시간: 1시간 10분

🧐 문제

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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 함수를 완성해주세요.

---

제한 사항

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

---

입출력 예

sequence	result
[2, 3, -6, 1, 3, -1, 2, 4]	10

---

입출력 예 설명

주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

---

✏️ 풀이 과정

펄스 수열은 따로 없이, 미리 정해진 수열이 있다고만 가정하자.

그렇다면 점화식은 아래와 같다.
\[dp[i] = max(dp[i-1] + dp[i], dp[i]);\]

여기에 펄스 수열의 규칙만 추가해서 구해주면 된다.

---

✏️ 나의 풀이

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
vector<vector<ll>> dp(2, vector<ll>(500001));

ll solution(vector<int> sequence) {
    //dp[0]쪽이 -로, dp[1]쪽이 +로 시작
    int flag = 1;
    dp[0][0] = sequence[0] * -flag;
    dp[1][0] = sequence[0] * flag;
    flag *= -1;
    
    ll answer = max(dp[0][0], dp[1][0]);
    for(int i=1; i<sequence.size(); i++) {    
        ll cur = sequence[i];
        
        dp[0][i] = max(dp[0][i-1] + cur * -flag, cur * -flag);
        dp[1][i] = max(dp[1][i-1] + cur * flag, cur * flag);
        
        flag *= -1;
        
        answer = max({answer, dp[0][i], dp[1][i]});
    }
    
    return answer;
}

---

✔️ 와사비님의 풀이

#include <string>
#include <vector>
using namespace std;

long long solution(vector<int> sequence) {
    long long answer = 0;
    vector<long long> v(4,0);
    for(int i = 0 ; i < sequence.size(); ++i){

        v[0] += (i%2==0?1:-1) * sequence[i];
        v[1] += (i%2==0?-1:1) * sequence[i];

        if(v[0] > v[2]) v[2] = v[0];
        if(v[1] > v[3]) v[3] = v[1];

        if(v[0] < 0) v[0] = 0;
        if(v[1] < 0) v[1] = 0;

    }
    answer = max(v[2],v[3]);
    return answer;
}

🧐 분석

• 벡터를 500,001길이만큼 만들어두지 않는다.
  • 4칸만 배정하고, 각 펄스 수열이 2칸씩 나누어 가진다.
  • 2칸은 또 다시, 현재 값과 최대 값으로 나누어 가진다.
• flag를 그냥 삼항 연산자로 대체하였다.
  • 이게 훨씬 깔끔하다.

---

🪶 후기

30분은 어떻게 풀까 고민하는데 썼다.

문제를 보자말자 DP가 떠올라야 하는데,
세그먼트 트리라던가, 투포인터가 떠올랐다.

그 뒤로, 40분 중에 20분동안 핵심 구현은 끝냈다.
하지만, 로직에 허점이 있어서 고치느라 남은 20분을 썼다.

기본기 중의 기본기 문제였는데, 참 부끄럽다.

Programmers 카테고리 내 다른 글 보러가기