문제 링크
문제 설명
어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다.
펄스 수열이란 [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;
}
}
'알고리즘 > 다이나믹프로그래밍' 카테고리의 다른 글
[자바]백준 13699번 점화식[다이나믹 프로그래밍][엄탱] (2) | 2023.03.02 |
---|---|
[자바]백준 2670번 연속부분최대곱 [다이나믹프로그래밍][엄탱] (5) | 2023.03.01 |
[자바]백준 2491번 수열 [다이나믹프로그래밍][엄탱] (4) | 2023.03.01 |
[자바]백준 9656번 돌 게임2 [다이나믹프로그래밍][엄탱] (3) | 2023.03.01 |
[자바]백준 14916번 거스름돈[다이나믹프로그래밍][엄탱] (6) | 2023.02.28 |