[백준 16637번] 괄호 추가하기 (파이썬/python)

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

16637번: 괄호 추가하기

처음에 여러 시도를해봤다.

+ - * 사이의 우선순위를 내가 임의로 지정하면되지않을까? 싶었지만 불가능했다.

이 문제는 모든 경우를 완전탐색해서 답을 도출해야됐다.

내가 임의로 연산자 우선순위를 주고 싶지만 그럴경우 처리하지 못 하는 변수가 생긴다.

 

 

내가 푼 풀이법은

우선 사용할 연산자의 인덱스를 리스트 안에 넣어주고

그 리스트에 넣은대로 선 연산을 하고

그 후 선 연산한 상태의 숫자 배열을 계산해서 답을 도출한다.

그 후 답이 최대일때를 찾으면 된다

 

와 한 두시간걸린듯 ㅜㅜ 풀고나서 진짜 감격했다. 코드가 좀 더럽지만..

 

 

import sys
 
input = sys.stdin.readline
n = int(input())
num_str = input().strip()
visit = [0] * (n + 1)    
li = []
max_num = -9999999999999999999999999
if n == 1:
    max_num = int(num_str[0])
 
 
def result(li1):
    number = int(li1[0])
 
    for i in range(1, len(li1) - 1, 2):
        if li1[i] == '+':
            number += int(li1[i + 1])
        elif li1[i] == '-':
            number -= int(li1[i + 1])
        else:
            number *= int(li1[i + 1])
 
    return number
 
 
# 처음 들어온 연산자 먼저 계산해준다.
def first_cal(f_li):
    arr = []
    i = 0
 
    while i < len(num_str):
 
        if i in f_li:
            a = arr.pop()
            if num_str[i] == '+':
                num = int(a) + int(num_str[i + 1])
                arr.append(str(num))
                i += 2
            elif num_str[i] == '*':
                num = int(a) * int(num_str[i + 1])
                arr.append(str(num))
                i += 2
            elif num_str[i] == '-':
                num = int(a) - int(num_str[i + 1])
                arr.append(str(num))
                i += 2
        else:
            arr.append(num_str[i])
            i += 1
    return result(arr)
 
 
def calculate(x):
    global max_num
    if len(li) > 0:
 
        r = first_cal(li)
        if max_num < r:
            max_num = r
 
    if x == n:
        return
 
    # 연산자만 탐색, 선택된 연산자 인덱스를 넣어줌
    for i in range(x, n, 2):
 
        if visit[i] == 1:
            continue
        visit[i] = visit[i + 2] = 1
        li.append(i)
        calculate(i + 4)
        li.pop()
        visit[i] = visit[i + 2] = 0
 
 
calculate(1)
print(max_num)