[백준] 16637 - 괄호 추가하기 [Python(파이썬)]

문제

www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

풀이

기본적으로 브루트포스에 속하지만, 백트래킹을 적용하여 풀 수 있는 문제였다.

이 문제는 다음과 같은 부분 문제로 나눠볼 수 있다.

 

1) 현재 상태에서 괄호를 넣는 경우와 안 넣는 경우를 모두 검사한다.

2) 괄호를 취한 식을 계산한다.

 

1)부터 살펴보자. 여기선 이 문제의 제약 조건 중 "중첩된 괄호는 사용할 수 없다."에 주목해야 한다.

이 말은 괄호의 위치가 고정되어 있다는 뜻이다. 다시 말해, 주어진 식(f)에 포인터를 두고 이동시키면서 괄호 삽입 여부를 체크하면 된다.

 

괄호를 삽입하는 함수인 insert_bracket은 현재 인덱스(i)와 큐를 인수로 받는다.

이때, 현재 인덱스는 모두 피연산자를 가리키며 큐는 연산자와 피연산자, 그리고 괄호를 순차적으로 담는다.

"수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다"라는 제약조건 때문에 스택이 아닌 큐를 사용해야 한다.

 

괄호를 안 넣는다면 현재 큐에 현재 피연산자(f[i])와 다음 연산자(f[i+1])를 큐에 삽입한다.

반대로 괄호를 넣는다면 f[i], f[i+1], f[i+2] (여기서 f[i]와 f[i+2]는 피연산자이고 f[i+1]은 연산자이다.)를 계산하고, 그 결과값과 다다음 연산자(f[i+3])를 큐에 삽입한다.

 

인덱스가 n-3에 이르면 괄호를 한 번 더 추가하거나, 괄호를 추가하지 않는 2가지 선택지가 있다.

n-1에 이르면 괄호를 추가할 수 없으므로 1가지 선택지가 있다.

따라서 i==n-3, i==n-1 2가지 경우에 대해서 계산(cal_queue)을 해주면 된다.

 

2)에 해당하는 코드는 단순하므로 자세한 설명은 생략했다.

 

코드

import sys
sys.setrecursionlimit(10**6)

def cal_queue(queue):
    result = queue[0]
    for i in range(0, len(queue)-2, 2):
        post = queue[i+2]
        result = cal_nums(result, post, queue[i+1])
    return result

def cal_nums(pre: int, post: int, op: str) -> int:
    if op == "+":
        return pre + post
    elif op == "-":
        return pre - post
    else:
        return pre * post

def insert_bracket(i, q):
    if i == n-1:
        no_br = q + [f[i]]
        return cal_queue(no_br)
    if i == n-3: # 한 번 더 갈 수 있음
        no_br = q + [f[i], f[i+1]]
        temp = cal_nums(f[i], f[i+2], f[i+1])
        br = q + [temp]
        return max(insert_bracket(i+2, no_br), cal_queue(br))

    # 안 넣는 경우
    no_br = q + [f[i], f[i+1]]
    # 넣는 경우
    temp = cal_nums(f[i], f[i+2], f[i+1])
    br = q + [temp, f[i+3]]

    return max(insert_bracket(i+2, no_br), insert_bracket(i+4, br))

n = int(sys.stdin.readline().strip())
f = [int(x) if x != "+" and x != "-" and x != "*" else x for x in sys.stdin.readline().strip()]

print(insert_bracket(0, []))