[프로그래머스] 연속 펄스 부분 수열의 합 Lv3 JAVA [DP][엄탱]

문제 링크

프로그래머스

문제 설명

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

펄스 수열이란 [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 함수를 완성해 주세요.

입출력 예 설명

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

해설

DP 알고리즘은  '한번 계산한 작은 문제를 저장해 놓고 다시 사용' 한다는 특징을 갖고 있다.

해당 문제는 변수에 한번 계산한 작은 문제를 저장하면서 사용한다.

그렇기 때문에 이 문제는 DP 중에 가장 기본이라고 생각한다.

이 문제는 변수 하나에 저장하지만 난이도가 높아지면 1차원 배열 난이도가 더 높아질수록 2차원 배열, 3차원 배열에 저장하여 사용한다.

2차원, 3차원으로 넘어가면 DP가 고급 알고리즘이라고 불리는 이유를 알게 된다..

 

해당 문제에서 생각해야 할 부분은 연속 수열에서만 부분 수열의 합을 구하는 게 아닌 펄스 수열을 곱하고 그중에서 가장 큰 합을 구하고 또한 펄스 수열은 [1, -1, 1...] 혹은 [-1, 1, -1...] 두 가지를 생각해야 한다는 점이다.

 

가장 큰 핵심은 부분 수열의 합이 절대 0보다 작을 수 없다는 것이다.

이유는 수열 중에 원소를 하나만 가져온다면 음수, 0, 양수가 나올 수 있는데 이때 음수는 -1을 곱하면 양수가 되기 때문에 절대 답이 0보다 작을 수 없다.

 

이 부분을 이용해서 문제를 푸는 게 핵심이다.

펄스 수열을 곱해가면서 합을 구하는데 0 이하로 나오게 되면 dp를 초기화하고 다시 최댓값을 구해주면 된다.

 

이 문제는 바로 코드를 살펴보자.

코드

접근 과정

1. [1, -1, 1, -1...]을 순서대로 곱하는 부분 수열의 합을 기록하기(purse1)

2. [-1, 1, -1, 1 ...]을 순서대로 곱하는 부분 수열의 합을 기록하기(purse2) 

3. sequence를 완전 탐색 하면서 값에 펄스 부분 수열을 곱하여 purse1, purse2에 더해주기

4. purse1이나 purse2가 0보다 작아지면 0으로 만들어 주기(0보다 작을 수 없기 때문에)

5. purse1이나 purse2가 answer보다 커지면 answer 변경해 주기

 

class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        
        boolean isPlus = true;
        
        long purse1 = 0;
        long purse2 = 0;
        
        for (int num: sequence) {
            purse1 += isPlus ? num : -num;
            purse2 += isPlus ? -num : num;
            
            purse1 = Math.max(0, purse1);
            purse2 = Math.max(0, purse2);
            
            answer = Math.max(answer, Math.max(purse1, purse2));
            
            isPlus = !isPlus;
        }
        
        return answer;
    }
}