문제 설명
정수로 이루어진 배열이 하나 주어졌다고 가정해 보겠습니다. 우리는 배열의 특정 요소 array[i]를 그 제곱 값(array[i] * array[i])으로 바꾸는 연산을 딱 한 번 수행할 수 있습니다. 이 연산을 적용한 뒤 만들 수 있는 최대 부분 배열(subarray)의 합을 반환해야 하며, 부분 배열은 비어 있으면 안 됩니다.
예를 들어 입력이 다음과 같다면,
array = [4, 1, -2, -1]
출력은 17이 됩니다.
배열의 첫 번째 요소 array[0]을 제곱 값으로 바꾸면 배열은 [16, 1, -2, -1]이 됩니다. 이때 만들 수 있는 최대 부분 배열은 [16, 1]이며, 그 합은 16 + 1 = 17입니다.
해결 접근 방식
이 문제는 동적 계획법(DP)을 활용해 해결할 수 있습니다. 두 개의 DP 배열을 사용하는 것이 핵심입니다.
- dp1: 제곱 연산을 전혀 사용하지 않았을 때의 최대 부분 배열 합을 저장합니다(카데인 알고리즘과 유사).
- dp2: 제곱 연산을 정확히 한 번 사용했거나 아직 사용하지 않은 경우 중 최대 부분 배열 합을 저장합니다.
구체적인 단계는 다음과 같습니다.
- dp1 := 음의 무한대(-inf)만 담고 있는 새로운 리스트로 초기화
- dp2 := 음의 무한대(-inf)만 담고 있는 새로운 리스트로 초기화
- 배열의 각 요소 num에 대해 다음을 반복
- dp1의 끝에 max(dp1의 마지막 값 + num, num)을 추가
- dp2의 끝에 max(dp1의 뒤에서 두 번째 값 + num², num², dp2의 마지막 값 + num)을 추가
- dp2의 최댓값을 반환
예제 코드
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(array):
dp1 = [float('-inf')]
dp2 = [float('-inf')]
for num in array:
dp1.append(max(dp1[-1] + num, num))
dp2.append(max(dp1[-2] + num**2, num**2, dp2[-1]+num))
return max(dp2)
print(solve([4, 1, -2, -1]))입력
[4, 1, -2, -1]
출력
17
동작 원리
dp1은 일반적인 카데인 알고리즘처럼 현재 위치까지의 최대 부분 배열 합을 추적합니다. dp2는 세 가지 선택지를 비교합니다. 바로 이전까지 제곱 없이 쌓아 온 합에 현재 요소의 제곱을 더하는 경우, 현재 요소부터 새 부분 배열을 시작하면서 제곱을 적용하는 경우, 그리고 이미 제곱을 사용한 상태(dp2)에서 현재 요소를 그대로 더하는 경우입니다. 이렇게 하면 제곱 연산을 최대 한 번만 사용하면서도 모든 경우를 고려할 수 있으며, 최종적으로 dp2의 최댓값이 정답이 됩니다.