Programmers. 사칙연산

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 사칙연산

문제 풀이

dp 문제로 아마 코테에 출제되었다면 상당한 난이도를 자랑해 해결하지 못했을 문제라 생각한다. 처음에는 분할 정복으로 가능한 모든 경우의 수에 대해 탐색했으나 TLE를 출력하여 결국 write up을 볼 수 밖에 없었다.

피연산자에 대해 모아두고 i번째 피연산자에서 j번째 피연산자까지의 연산 결과를 저장하는 2차원 dp 배열을 생성하되 길이는 피연산자의 개수로 제한한다.

덧셈의 최댓값은 최댓값 + 최댓값이나 뺄셈의 최댓값은 최댓값 - 최솟값으로 최댓, 최솟값을 모두 관리해야 하기에 dp 배열을 2개 생성해야 한다.

• 최댓값과 최솟값을 저장할 dp 배열을 2개 생성
• 각 피연산자 좌표에 대해 dp[i][i]=피연산자 값저장
• 연산 범위 저장을 위해 1부터 피연산자의 개수만큼 반복문 정의
• 연산 시작 지점 지정을 위해 0부터 피연산자 길이 - 연산범위에 대해 반복문 정의
• 연산 마지막 범위 좌표를 위해 시작지점 + 연산 범위 정의
• 연산 시작지점부터 마지막 범위까지의 반복문 정의, 연산좌 좌표를 정의해야 함.
• 연산자의 상태에 따라 최댓값, 최솟값 정의
• 마지막까지 순회 수 0부터 마지막 피연산자까지의 결과를 의미하는 좌표값을 반환한다.

python 코드

def solution(arr):
    INF = float('inf')
    min_dp = [INF for _ in range(len(arr) // 2 + 1)]
    max_dp = [-INF for _ in range(len(arr) // 2 + 1)]
    for i in range(len(arr) // 2 + 1):
        min_dp[i][i] = arr[i * 2 + 1]
        max_dp[i][i] = arr[i * 2 + 1]
    for c in range(1, len(max_dp)):
        for i in range(len(max_dp) - c):
            j = i + c
            for k in range(i, j):
                if arr[k * 2 + 1] == "+":
                    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 arr[k * 2 + 1] == "-":
                    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][-1]