문제 개요
nums라는 숫자 리스트가 주어졌을 때, 숫자들 사이에 +(덧셈), -(뺄셈), *(곱셈)과 같은 이항 연산자를 자유롭게 삽입하고, 필요한 곳에 유효한 괄호를 추가하여 만들 수 있는 식 중에서 최댓값을 찾는 것이 목표입니다.
예를 들어 nums = [-6, -4, -10]이 입력으로 주어진다면, 식을 ((-6) + (-4)) * -10처럼 구성할 수 있습니다. 이 식의 결과는 100이므로 출력값은 100이 됩니다.
접근 방법: 동적 계획법(DP)
이 문제는 동적 계획법(Dynamic Programming)을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 구간에서 만들 수 있는 값의 최솟값과 최댓값을 함께 저장하는 것입니다. 음수 × 음수 = 양수처럼, 전체 최댓값을 만들려면 구간별 최솟값 정보도 필요하기 때문입니다.
구체적인 해결 단계는 다음과 같습니다.
- OPS := 사용할 연산자 목록 [+, -, *]
- N := 배열 A의 크기
- A의 모든 원소가 0이라면 0을 반환합니다.
- dp(i, j) 함수를 정의합니다.
- i == j인 경우, 즉 구간에 숫자가 하나만 남았다면 (A[i], A[i]) 쌍을 반환합니다.
- low := 무한대(inf), high := -무한대(-inf)로 초기화합니다.
- k를 i부터 j-1까지 반복하며 구간을 분할합니다.
- 왼쪽 부분 dp(i, k)의 각 결과값 left에 대해
- 오른쪽 부분 dp(k + 1, j)의 각 결과값 right에 대해
- OPS의 각 연산자 op로 res := left op right를 계산하고,
- res가 low보다 작으면 low를, res가 high보다 크면 high를 갱신합니다.
- (low, high) 쌍을 반환합니다.
- 메인 로직에서는 ans := dp(0, N - 1)을 호출한 뒤, ans의 두 번째 값(최댓값)을 반환합니다.
파이썬 구현 예제
import operator
class Solution:
def solve(self, A):
OPS = [operator.add, operator.sub, operator.mul]
N = len(A)
if not any(A):
return 0
def dp(i, j):
if i == j:
return [A[i], A[i]]
low = float("inf")
high = float("-inf")
for k in range(i, j):
for left in dp(i, k):
for right in dp(k + 1, j):
for op in OPS:
res = op(left, right)
if res < low:
low = res
if res > high:
high = res
return [low, high]
return dp(0, N - 1)[1]
ob = Solution()
nums = [-6, -4, -10]
print(ob.solve(nums))
입력
[-6, -4, -10]
출력
100
동작 원리 정리
dp(i, j) 함수는 인덱스 i부터 j까지의 구간에서 만들 수 있는 값들의 최솟값과 최댓값을 쌍(pair)으로 반환합니다. 구간을 가능한 모든 위치(k)에서 둘로 나눈 뒤, 왼쪽 결과와 오른쪽 결과를 세 가지 연산자로 조합하면서 최솟값(low)과 최댓값(high)을 지속적으로 갱신합니다.
특히 음수가 포함된 입력에서는 "음수 ÷ 음수"가 아니라 "음수 × 음수"처럼 최솟값끼리 곱해 오히려 더 큰 양수가 되는 경우가 발생할 수 있으므로, 최댓값만 추적하지 않고 최솟값도 함께 관리하는 것이 이 알고리즘의 핵심 포인트입니다.
시간 복잡도는 구간의 수 O(N²)에 각 구간마다 분할·조합 연산이 더해져 대략 O(N³) 수준이며, 재귀 + 메모이제이션 구조로 불필요한 중복 계산을 줄일 수 있습니다.