문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/161988
비교적 접근하기 쉬웠던 DP 문제였습니다.
알고리즘은 아래와 같습니다.
1. 펄스 수열은 1로 시작하는 경우와 -1로 시작하는 경우 두 가지입니다.
1.1 따라서 주어진 sequence에 대해 두 가지 펄스 수열을 구하고 이들의 부분 수열 합 중 최대 값을 구하면 됩니다.
2. cache[i]를 i번째 인덱스까지 탐색했을 때 최댓값을 저장하는 dp 배열로 정의했을 때 점화식은 아래와 같습니다.
2.1 v가 펄스 부분 수열이라고 가정했을 때 cache[i] = max(v[i], cache[i -1] + v[i])
2.2 연속성을 보장하기 위해 v[i]는 반드시 포함해야 하기 때문에 i 번째 원소부터 시작하는 부분수열의 합과 기존 부분 수열에 i 번째 원소를 포함할지만 판단하면 됩니다.
2.3 단, 주어진 sequence의 크기가 1일 경우에는 예외처리를 해줘야 합니다.
3. 1.1에서 구한 두 가지 펄스 수열에 대해 2번 과정을 수행한 결과를 반환해 주면 됩니다.
개발환경: Programmers IDE
지적, 조언, 질문 환영합니다! 질문 남겨주세요~
반응형
'알고리즘 > programmers' 카테고리의 다른 글
[Programmers] 도넛과 막대 그래프 (4) | 2024.01.06 |
---|---|
[Programmers] 가장 많이 받은 선물 (0) | 2024.01.05 |
[Programmers] 표 병합 (0) | 2023.12.31 |
[Programmers] PCCE 기출문제 모음 (0) | 2023.12.18 |
[Programmers] 등대 (0) | 2023.12.13 |