16639: 괄호 추가하기 3

DP [Dynamic Programming], 동적계획법

• DP: 하나의 문제를 작은 여러개의 문제들로 나누어 부분의 결과를 저장해 재사용하는 것으로, 메모리 사용을 효과적으로 개선할 수 있다.  
• DP의 유형  

•  1) top-down: 큰 문제부터 시작해서 작은 문제로 쪼개가면서 답을 내는 과정이다. 이때, 한번 계산된 값들은 저장해두고 또 필요한 경우 이를 참고해 재사용한다   
•  2) bottom-up: 작은 문제들에 대한 값을 미리 모두 저장해두고 작은 문제에서부터 큰 문제로 가면서 답을 낸다.  

• DP 사용조건 

       1) overlapping subproblems (겹치는 문제): 동일한 작은 문제가 반복적으로 나타나 그 값을 재사용할 수 있는 경우

       2) obtimal substructure (최적 부분 구조): 작은 문제들의 최적의 값들로 전체 문제의 최적의 값을 보장할 수 있는 경우 

---

'''

구현해야하는 것 (DP, bottom-up)

1. 숫자 인덱스(짝수인덱스)로 이루어진 연산 테이블 작성해서 최대, 최소값 저장   

2. 괄호의 갯수와 위치에 제한이 없으므로 bottom-up방식으로 작은 단위의 연산값부터 확인하여 저장한 뒤 이를 이용해 점차 긴 연산 수행하는 방식으로 마지막에는 최종 수식에 대한 최대/최소 값을 구할 수 있다.

 

**주의사항**

테이블에서 bottom up 으로 작은 문제들의 값부터 저장하기 위해 왼쪽아래->오른쪽 위 로의 방향으로 연산을 진행해야 한다 .

'''

(ex) 수식이 다음과 같을 때

3+8*7-9*2

	3	8	7	9	2
3	3, 3	(3->3)+(8->8)	(3->8)+(8->7)		<최종 결과>
8		8, 8	(8->8)+(7->7)	...
7			7, 7	(7->7)+(9->9)	...
9				9, 9	(9->9)+(2->2)
2					2, 2

 

 

# boj-16639
# DP-bottom up: 하나의 문제를 작은 여러개로 나누어 최적부분구조로 나누어 해결하는 방식
n = int(input())
math_oper = list(input()) # input(): 한 음절단위로 입력받음, input().split(): 화이트스페이스 기준으로 나눔
num = n//2 + 1
num_lst = [math_oper[k] for k in range(0, n, 2)]
oper = [math_oper[k] for k in range(1, n-1, 2)]
dp_table = [[[0, 0] for _ in range(num)] for _ in range(num)]
result = 0

def calc(num1, num2, idx):
    if oper[idx] == '+':
        out = num1 + num2
    elif oper[idx] == '-':
        out = num1 - num2
    elif oper[idx] == '*':
        out = num1 * num2

    return out

for j in range(num):
    for i in range(num-j):
        if j == 0: # 동일 수->동일 수
            dp_table[i][i+j] = [int(num_lst[i]), int(num_lst[i])]
        else:
            mininum = 2**(31)
            maximum = -2**(31)
            for k in range(i, i+j): # num1-> num2 답 중에서 두 부분으로 나누는 경우의 수
                tmp_result = [-1 for _ in range(4)]
                tmp_result[0] = calc(dp_table[i][k][0], dp_table[k+1][i+j][0], k)
                tmp_result[1] = calc(dp_table[i][k][0], dp_table[k+1][i+j][1], k)
                tmp_result[2] = calc(dp_table[i][k][1], dp_table[k+1][i+j][0], k)
                tmp_result[3] = calc(dp_table[i][k][1], dp_table[k+1][i+j][1], k)

                min_ = min(tmp_result)
                max_ = max(tmp_result)
                if mininum > min_:
                    mininum = min_
                if maximum < max_:
                    maximum = max_

            dp_table[i][i+j] = [mininum, maximum]

print(dp_table[0][num-1][1])