16639번: 괄호 추가하기 3 / gold 1 / DP

https://www.acmicpc.net/problem/16639

16639번: 괄호 추가하기 3

'''
16639번: 괄호 추가하기 3 / gold 1 / DP
'''
import sys

input = sys.stdin.readline


# a와 b를 계산해서 리턴하는 함수
def calculator(a, op, b):
    if op == '-':
        return a - b
    elif op == '+':
        return a + b
    elif op == '*':
        return a * b


# dp[x][y] 자리의 최솟값 최대값 구해서 리턴하는 함수
def find_min_max(x, y, i, j):
    value_list = []
    while True:
        if j == y:
            break
        value_list.append(calculator(dp[x][j][0], op_list[j], dp[i][y][0]))
        value_list.append(calculator(dp[x][j][0], op_list[j], dp[i][y][1]))
        value_list.append(calculator(dp[x][j][1], op_list[j], dp[i][y][0]))
        value_list.append(calculator(dp[x][j][1], op_list[j], dp[i][y][1]))
        i += 1
        j += 1
    return min(value_list), max(value_list)


# 수식길이: n, 수식: expression 입력받기
n = int(input())
expression = input().rstrip()
# 연산자 리스트, 정수 리스트 따로 분류하기
op_list = []
num_list = []
for i in range(len(expression)):
    if i % 2 == 0:
        num_list.append(int(expression[i]))
    else:
        op_list.append(expression[i])
num_cnt = len(num_list)
# dp 리스트 만들기
dp = [[[0, 0] for _ in range(num_cnt)] for _ in range(num_cnt)]
# dp 리스트 채우기
for x in range(num_cnt - 1, -1, -1):
    j = x
    for y in range(x, num_cnt):
        if x == y:
            dp[x][y][0] = num_list[x]
            dp[x][y][1] = num_list[x]
        else:
            i = x + 1
            max_value, min_value = find_min_max(x, y, i, j)
            dp[x][y][0] = min_value
            dp[x][y][1] = max_value
# 출력하기
print(max(dp[0][-1]))

코드 리뷰

처음 시도한 접근법

- 주어진 연산자들에게 모두 우선순위를 매기는 로직을 생각했습니다.

- 모든 우선순위에 대한 경우의 수들을 하나씩 실행해서 최댓값을 구하는 방식!

- 하지만, 코드를 짜면서 제가 생각한 로직이 시간초과가 걸릴 것이라는 생각이 들었습니다.

- 결국 문제를 푸는데 1시간 30분 이상 소요가 되어 구글링을 하게 되어 정답판정 코드들을 보게 되었습니다.

 

DP로 접근해서 문제를 푸는 방식을 이해했고, 제가 이해한대로 코드를 짜게 되었습니다.

 

어려운 부분

1. DP 리스트 생성 : 수식의 특정 부분 만의 최댓값 최솟값을 담는 의미로 dp 리스트를 설계하고 만들어야 합니다.

2. DP 리스트 채우는 순서와 방식 

   - 순서 :  bottom-up 방식으로 최솟값과 최댓값을 채웁니다.

   - 방식 : dp[x][y][0], dp[x][y][1] 을 채우기 위해서는, 이전에 채웠던 dp들을 활용해야 하므로 i, j 변수를 지정했습니다.