[BOJ] Q16639 괄호 추가하기 3

[BOJ] Q16639 괄호 추가하기 3

Question

Language: Python

Difficulty: Gold 1

해당 문제는 얼핏 봐서는 q16637,q16638와 유사한 형태의 문제 같지만 자세히 보면 전혀 다른 방향으로 접근해야된다.

3+8*7-9*2의 경우는 아래와 같이 분할해서 생각해볼 수 있다. 나눠진 연산식들 중에서 최대값을 저장해나가면 방식이구나? 라고 생각할 수 있다. 해당 유형은 [q11049](/codetest/dp11049/]와 유사한 형태의 문제이다.

하지만, 여기서 한 번더 생각할 부분 이 있다. 다음과 같이 무조건 최대값을 저장하면 안되는 이유가 곱연산이 있기 때문이다. 그렇게 되면, 음수끼리의 곱이 양수가 되면서 양수끼리의 곱보다 커지는 경우가 발생할 수 있다. 따라서, 아래와 같이 4가지의 경우에 대해서 모두 생각해야 되며, 최대값, 최소값을 고려하면서 Bottom-Up 방식의 DP로 해결해야된다.

#최소,최대 저장
di=[[[0,0] for _ in range(num+1)] for _ in range(num+1)]

"""
1.최소 op 최소
2.최소 op 최대
3.최대 op 최대
4.최대 op 최대
를 비교하면서 최소,최대를 구해야한다.
"""
for k in range(i,j):
    tmp.append(calculate(di[i][k][0],di[k+1][j][0],operators[k]))
    tmp.append(calculate(di[i][k][0],di[k+1][j][1],operators[k]))
    tmp.append(calculate(di[i][k][1],di[k+1][j][0],operators[k]))
    tmp.append(calculate(di[i][k][1],di[k+1][j][1],operators[k]))
di[i][j][0]=min(tmp)
di[i][j][1]=max(tmp)

Solution

from math import inf
max_result=-inf

def calculate(op1,op2,operator):
    if operator == "+":
        return op1+op2
    elif operator =="-":
        return op1-op2
    elif operator == "*":
        return op1*op2
         
def solution():
    operands=[]
    operators=[]

    for segment in expression:
        if "0"<=segment<="9":
            operands.append(int(segment))
        else:
            operators.append(segment)


    di=[[[0,0] for _ in range(num+1)] for _ in range(num+1)]
    
    for i in range(num+1):
        di[i][i][0]=operands[i]
        di[i][i][1]=operands[i]
    
    for diagonal in range(1,num+1):
        for i in range(num-diagonal+1):
            j=i+diagonal
            tmp=[]
            for k in range(i,j):
                tmp.append(calculate(di[i][k][0],di[k+1][j][0],operators[k]))
                tmp.append(calculate(di[i][k][0],di[k+1][j][1],operators[k]))
                tmp.append(calculate(di[i][k][1],di[k+1][j][0],operators[k]))
                tmp.append(calculate(di[i][k][1],di[k+1][j][1],operators[k]))
            di[i][j][0]=min(tmp)
            di[i][j][1]=max(tmp)


    return max(di[0][num])
if __name__ == "__main__":
    length=int(input())
    expression=list(input())
    num=length//2 
    print(solution())