[프로그래머스] 사칙연산

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1843

💻 문제 풀이 : Python

def solution(arr):
    n = len(arr) // 2 + 1 # Number of digits
    num_arr = [int(arr[i]) for i in range(0, len(arr), 2)] # Extract only digits
    op_arr = [arr[i] for i in range(1, len(arr), 2)] # Extract only operators
    
    # Initializes DP tables for max and min values
    max_dp = [[-float('inf')] * n for _ in range(n)]
    min_dp = [[float('inf')] * n for _ in range(n)]
    
    # Base case : single number
    for i in range(n):
        max_dp[i][i] = num_arr[i]
        min_dp[i][i] = num_arr[i]
    
    # Iterate over length of subexpressions(1 ~ n-1)
    for length in range(1, n):
        for i in range(n - length):
            j = i + length
            
            # Evaluate all possible subexpressions
            for k in range(i, j):
                if op_arr[k] == '+':
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k+1][j])
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k+1][j])
                elif op_arr[k] == '-':
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] - min_dp[k+1][j])
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] - max_dp[k+1][j]
                
    return max_dp[0][n-1]

ref ) Chat GPT 🔥

---

📌 memo

풀이...

1. 제일 직관적으로 드는 생각은 ( )를 조합으로 선택하는 방법
   => N 개의 연산자가 있을때, N 개의 순서를 정하는 법
   => 최대 100개의 연산자가 있으므로, 100! = 대략 10^156

2. 왜 DP 일까...?
   현재 주어진 배열에서 length 가 1일때
   ...
   => n-1 일때까지 대략 O(n) 을 순회하면 답이 나온다...?
   => 엄밀하게는 O(n^3)이나, 최대가 100이므로 1,000,000 이므로 풀이 가능

3. DP 배열을 어떻게 만들까?
   => 이전에 서술했듯 length 가 1~ n-1일때까지 순회