문제 보기 · Level 4 · 동적계획법(Dynamic Programming) · 정답률 20% · 푼 사람 4,259명 (2026-09-30 기준)1

문제

숫자와 +, -가 번갈아 들어 있는 식이 배열로 주어진다. 연산 순서(괄호 치는 방법)를 바꿔 얻을 수 있는 계산 결과 중 최댓값을 돌려준다.

  • 배열 길이 3 ~ 201(홀수), 숫자 2 ~ 101개
  • 숫자는 1 ~ 1,000

풀이

막히면 한 단계씩 펼친다.

필요한 개념

구간 DP: 숫자 i ~ j로 이루어진 부분식의 답을, 마지막으로 계산하는 연산자 자리로 나눠 더 짧은 부분식의 답으로 만든다.

1단계 · 작은 예로 손으로 풀기

1 − 3 + 5 − 8의 괄호 치는 방법은 다섯 가지이고, 결과는 −5, −15, 1, 1, −5다. 최댓값은 1((1 − (3 + (5 − 8))))이다.

식 전체를 마지막으로 계산하는 연산자가 첫 −라면 결과는 “1 − (3 + 5 − 8의 어떤 결과)”다. 이 값을 가장 크게 하려면 뒤쪽을 가장 작게 만들어야 한다. 그래서 부분식마다 최댓값만이 아니라 최솟값도 알아야 한다.

2단계 · 가장 단순한 방법과 그 속도

괄호 치는 방법은 카탈란 수만큼 있다. 숫자 101개면 C₁₀₀으로 어림없이 많다.

괄호 치는 방법 하나는 숫자를 잎, 연산자를 내부 노드로 둔 정 이진 트리(자식이 0개나 2개인 트리) 하나다. 잎이 n개인 정 이진 트리의 모양 수가 Cₙ₋₁이고(재귀적 정의와 구조적 귀납법), 3단계의 “마지막 연산자”는 이 트리의 뿌리다.

3단계 · 핵심 아이디어
  • 상태: mx[i][j], mn[i][j] = 숫자 i ~ j 부분식의 최댓값, 최솟값.
  • 마지막 연산자 k로 나누기: 앞 i ~ k, 뒤 k + 1 ~ j.
    • +면: 최대 = 앞 최대 + 뒤 최대, 최소 = 앞 최소 + 뒤 최소
    • −면: 최대 = 앞 최대 − 뒤 최소, 최소 = 앞 최소 − 뒤 최대
  • 순서: 짧은 구간부터 채운다. 답은 mx[0][n − 1].
4단계 · 코드 흐름
  1. 숫자 목록과 연산자 목록으로 나눈다.
  2. 길이 1 구간은 숫자 그대로(최대 = 최소).
  3. 길이 2 ~ n 구간마다, 나누는 자리 k마다 위 규칙으로 후보를 만들어 최대·최소를 갱신한다.
  4. mx[0][n − 1]을 돌려준다.
5단계 · 파이썬 코드 
def solution(arr):
    nums = [int(x) for x in arr[0::2]]
    ops = arr[1::2]                            # ops[k]: nums[k]와 nums[k+1] 사이
    n = len(nums)
    INF = float("inf")
    mx = [[-INF] * n for _ in range(n)]
    mn = [[INF] * n for _ in range(n)]
    for i in range(n):
        mx[i][i] = mn[i][i] = nums[i]
    for length in range(2, n + 1):             # 짧은 구간부터
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):              # 마지막으로 계산하는 연산자
                if ops[k] == "+":
                    hi = mx[i][k] + mx[k + 1][j]
                    lo = mn[i][k] + mn[k + 1][j]
                else:
                    hi = mx[i][k] - mn[k + 1][j]
                    lo = mn[i][k] - mx[k + 1][j]
                if hi > mx[i][j]:
                    mx[i][j] = hi
                if lo < mn[i][j]:
                    mn[i][j] = lo
    return mx[0][n - 1]
  • arr[0::2]: 0번째부터 두 칸씩, 곧 숫자들이다. arr[1::2]는 연산자들이다.
6단계 · 실행 추적

1 − 3 + 5 − 8 (숫자 0 ~ 3)

구간 나누는 자리별 (최대, 최소) 최대 최소
[0, 1] 1 − 3   −2 −2
[1, 2] 3 + 5   8 8
[2, 3] 5 − 8   −3 −3
[0, 2] 1 − 3 + 5 1 − (8): (−7, −7) / (−2) + 5: (3, 3) 3 −7
[1, 3] 3 + 5 − 8 3 + (−3): (0, 0) / 8 − 8: (0, 0) 0 0
[0, 3] 전체 1 − [1, 3]: (1, 1) / [0, 1] + [2, 3]: (−5, −5) / [0, 2] − 8: (−5, −15) 1 −15

답은 1이다.

7단계 · 복잡도와 흔한 실수

숫자 n개에 \(O(n^3)\), n = 101이면 약 17만 번이다. 재 보니 금방 끝났다.

  • 최댓값만 들고 다녀 − 뒤쪽의 최솟값을 모른다. 1 − 1 − 1 − 1에서 최댓값만 쓰면 0이 나오지만, 답은 1 − ((1 − 1) − 1) = 2다.
  • −의 최솟값을 “앞 최소 − 뒤 최소”로 잘못 계산한다. 뒤를 최대로 빼야 가장 작다.
  • 표를 짧은 구간부터 채우지 않는다.
검증: 문제의 예시 2개를 통과했고, 예시 1의 다섯 결과, 6단계 표의 최대·최소, 최댓값만 들고 다니면 틀리는 예를 코드로 확인했다. 무작위 식 2,000개(숫자 7개 이하)에서 “괄호 치는 방법을 모두 만들어 결과를 모은” 풀이의 최댓값과 같았다 — 31_pg1843_p1.py

  1. 프로그래머스 스쿨, “사칙연산” (https://school.programmers.co.kr/learn/courses/30/lessons/1843), 2026-09-30 조회. ↩