사칙연산

문제

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

이 문제 푸는데 꼬박 이틀 걸렸다^^,, 처음 접근 방식은 비교적 일찍 생각난 반면, 코드 구현 과정에서 자!!!!!! 꾸 꼬여서.. 중꺾마로 끝까지 풀어냈슴다 🫠 후

접근 방식

여기서 해결하고자 하는 문제의 단위는 "수1 연산자 수2" 구조다. 왜 그렇게 되는지 알아보자.

문제에서 주어진 예시 1 - 3 + 5 - 8를 쪼개보면 다음과 같다:

뭘 먼저 묶는지에 따라 연산 결과가 달라지기 때문에, 하나의 묶음을 문제의 단위라고 생각하면 "계산 결과 1(수) 연산자 계산 결과 2(수)" 구조일 것이다.

여기서 최종 연산의 최댓값을 구하랬으니, 최댓값만 계속 들고 가면 될까 ?
아니다. 뺄셈을 고려해 최댓값, 최솟값을 같이 들고가야 한다.

뺄셈의 경우, 연산의 최댓값을 보장하기 위해서는 최댓값 - 최솟값 형태기 때문이다.

결국 연산 결과 중 최대, 최솟값을 가져가면서 하나의 묶음 수행하면 되는 형태다.

연산 정리:

- 뺄셈)
	- 최대 결과 = 최댓값 - 최솟값
    - 최소 결과 = 최솟값 - 최댓값
- 덧셈)
	- 최소 결과 = 최솟값 + 최솟값
    - 최대 결과 = 최댓값 + 최댓값

코드

INF = int(1e9)


def solution(arr):
    operator, operands = [], []  # 연산자, 피연산자 모음
    for x in arr:
        if x.isdigit():
            operands.append(int(x))
        else:
            operator.append(x)
    n = len(operands)

    min_dp = [[INF] * n for _ in range(n)]
    max_dp = [[-INF] * n for _ in range(n)]
    vis = [[False] * n for _ in range(n)]  # 중복 연산 방지
    for i in range(n):
        min_dp[i][i] = operands[i]
        max_dp[i][i] = operands[i]
        vis[i][i] = True

    # bottom-up
    for cnt in range(2, n + 1):
        for i in range(0, n - cnt + 1):
            for j in range(i + 1, i + cnt):
                if vis[i][j]:
                    continue
                vis[i][j] = True

                for k in range(cnt - 1):
                    if operator[i + k] == '-':
                        min_dp[i][j] = min(min_dp[i][i + k] - max_dp[i + k + 1][j], min_dp[i][j])
                        max_dp[i][j] = max(max_dp[i][i + k] - min_dp[i + k + 1][j], max_dp[i][j])
                    else:
                        min_dp[i][j] = min(min_dp[i][i + k] + min_dp[i + k + 1][j], min_dp[i][j])
                        max_dp[i][j] = max(max_dp[i][i + k] + max_dp[i + k + 1][j], max_dp[i][j])

    return max_dp[0][n - 1]

처음에는 top-down 구조가 직관적으로 떠올라, dfs로 풀다가 33.3/100.0 나왔는데.. 확실히 이 부분이 약하구나 싶다. 휴 어렵 🫠,,

다음으로 반복문을 활용한 bottom-up 구조로 풀이를 변경했는데 경계값 처리에서 걸려서 한차례 디버깅 파티(..)와 중복으로 연산되는 문제 때문에 효율성이 전부 걸려서 방문 처리를 추가했다. 이 부분 분명 최적화 시킬 게 있을 거 같은데 흠 .. 🧐