[프로그래머스] 사칙연산 (Python/파이썬)

<문제 링크>

https://school.programmers.co.kr/learn/courses/30/lessons/1843

프로그래머스

 

<풀이 전략>

1. 매우 어려웠던 dp + 분할정복 문제

2. 연산자를 기준으로 앞 뒤 구간을 나누어서 계산해주면 된다. (구간합과 유사)

10개의 피연산자가 있다고 가정할 때 다음과 같다

[1] ~ [2 ~ 10]
[1 ~ 2] ~ [3 ~ 10]
[1 ~ 3] ~ [4 ~ 10]
...
[1 ~ 9] ~ [10]

3. - 연산자가 있으므로 최댓값 테이블과 최솟값 테이블 두 개의 배열을 만든다

4. 구간의 길이 (1 ~ N - 1)마다 반복문을 돌면서 해당 구간 내에서 다시 시작(i)과 끝(j) 피연산자에 사이에서 반복문을 돌면서(k) 구간의 누적 연산 (최소/최대)값을 구해주면 된다.

5. 결과적으로 최댓값 테이블 dp_max[0][N - 1]은 arr의 첫번쨰 피연산자부터 마지막 피연산자 구간, 즉 전체 구간의 최댓값을 값으로 가지게 된다.

6. dp라는 걸 알고 푼 상태에서 최솟값과 최댓값으로 나눠서 구간합으로 접근해야겠다는 것까지는 생각했는데 점화식이나 dp 테이블을 어떻게 짜야될지 감이 안 와서 검색해서 풀었다. 아마 사전 정보 없이 시험장에서 봤다면 절대 못 풀었을 문제... 열심히 공부해야겠다

 

<정답 코드>

import sys

# 230125 프로그래머스 사칙연산

def solution(arr):
    answer = -1

    N = len(arr)//2 + 1
    INF = sys.maxsize

    # dp 테이블 초기화 (범위에 따른 최솟값 최댓값 연산 테이블)
    # arr[i][j] = i번째 피연산자 ~ j번째 피연산자까지 연산의 최솟값/최댓값
    dp_min = [[INF for _ in range(101)] for _ in range(101)]
    dp_max = [[-INF for _ in range(101)] for _ in range(101)]

    for i in range(0, N):
        dp_min[i][i] = int(arr[i * 2])
        dp_max[i][i] = int(arr[i * 2])

    # 계산 범위
    for calculate_range in range(1, N):
        # i: 시작 피연산자
        for i in range(0, N - calculate_range):
            # j: 마지막 피연산자
            j = calculate_range + i

            for k in range(i, j):

                # + 연산자
                if arr[k*2 + 1] == '+':
                    dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j])
                    dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j])
                # - 연산자
                else:
                    dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] - dp_min[k + 1][j])
                    dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] - dp_max[k + 1][j])

    answer = dp_max[0][N - 1]

    return answer