[BOJ] Q16637 괄호 추가하기

[BOJ] Q16637 괄호 추가하기

Question

Language: Python

Difficulty: Gold 4

주어진 연산식에 대해서, 괄호를 추가하면서 해당 연산식이 가질 수 있는 최대값을 구하는 문제이다. 문제에서 연산식을 계산하는 방식은 일반적인 연산자 우선순위에 따른 연산이 아닌 왼쪽에서 오른쪽으로 순서대로 이어가는 방식이다.

이때, 괄호를 치게 되면, 괄호 안에 있는 값을 먼저 계산하게 된다. 모든 연산자에 대해서 괄호를 치냐/안 치냐를 조사하면서 연산식을 계산하는 Backtracking 문제이다. 또한, 문제에 주어진을 통해서, 연속되게 괄호를 사용하지 못하는 것을 알 수 있다. 따라서, 이전 연산자에 괄호를 적용했는지를 판단하는 변수를 활용해야한다.

풀이는 아래와 같이 동작하게 된다.

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 processing_parenthesis_and_calculate(operands,operators):
    result=operands[0]
    for index in range(len(operators)):
        result=calculate(result,operands[index+1],operators[index])

    return result

def recursion(count,remaining_operands,remaining_operators,is_Used):
    global max_result

    if count==num:
        if is_Used:
            max_result=max(max_result,processing_parenthesis_and_calculate(remaining_operands,remaining_operators))
        #마지막 항에 대해서 괄호를 사용하지 않은 경우 마지막 피연산자도 추가한다.
        else:
            max_result=max(max_result,processing_parenthesis_and_calculate(remaining_operands+[operands[count]],remaining_operators))

        return
    #이전에 괄호를 취하지 않은 경우
    if is_Used==False:
        #현재 괄호를 취하는 경우 괄호 계산후에 해당 피연산자항 추가
        recursion(count+1,remaining_operands+[calculate(operands[count],operands[count+1],operators[count])],remaining_operators,True)
        #현재 괄호를 취하지 않는 경우 피연산자와 연사자항 추가
        recursion(count+1,remaining_operands+[operands[count]],remaining_operators+[operators[count]],False)

    #이전에 괄호를 취한 경우
    else:
        # 연산자만 추가한다.
        recursion(count+1,remaining_operands,remaining_operators+[operators[count]],False)   
         
def solution():

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

    parenthesized=[False] * len(operators)
    recursion(0,[],[],False)
    
    print(max_result)
        
if __name__ == "__main__":
    length=0
    expression=""
    num=0
    operands=[]
    operators=[]

    length=int(input())
    expression=list(input())
    num=length//2 
    solution()