https://school.programmers.co.kr/learn/courses/30/lessons/161988
문제 해결 과정
착안
동적계획법(dynamic programming)을 통해 부분 수열의 합을 구하는 알고리즘을 응용하여 펄스 부분 수열의 합을 구한다.
구현
이전 포스트에서 사용한 방법을 동일하게 적용하되, 원래 수열에 곱할 수 있는 펄스 수열은 1 또는 -1로 시작하는 두 가지의 경우가 있으므로, 원래 수열에 1과 -1로 시작하는 각각의 펄스 수열을 길이만큼 곱한 수열에 대해 부분 수열의 합을 구하는 방식으로 문제를 해결하였다.
예시) 주어진 수열이 1, 2, 3, 4, 5 인 경우
- 1, -2, 3, -4, 5 에 대한 부분 수열의 합 중 최댓값을 계산
- -1, 2, -3, 4, -5 에 대한 부분 수열의 합 중 최댓값을 계산
- 두 값 중 큰 값을 return
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <vector>
using namespace std;
long long pulsify(vector<int> sequence, int sgn)
{
long long maxSum = 0;
long long sum = 0;
int idx = 0;
while (idx < (int)sequence.size())
{
int num = sgn * sequence[idx];
if (sum + num > 0)
{
sum += num;
if (maxSum < sum)
maxSum = sum;
}
else
sum = 0;
sgn *= -1;
idx++;
}
return maxSum;
}
long long solution(vector<int> sequence)
{
long long num1 = pulsify(sequence, 1);
long long num2 = pulsify(sequence, -1);
return num1 > num2 ? num1 : num2;
}
실행 결과
'C++ 코딩 문제 풀이 > 프로그래머스' 카테고리의 다른 글
[Programmers] 괄호 회전하기 (0) | 2023.09.07 |
---|---|
[Programmers] 호텔 대실 (0) | 2023.09.07 |
[Programmers] 멀리 뛰기 (0) | 2023.08.30 |
[Programmers] 예상 대진표 (1) | 2023.08.28 |
[Programmers] N개의 최소공배수 (0) | 2023.08.27 |
댓글