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

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

# 괄호 추가하기
import copy
import sys
input = sys.stdin.readline
MAX = sys.maxsize

N = int(input())
arr = input().strip()
nums = []
op = []
for i, x in enumerate(arr):
    if i % 2 == 0:
        nums.append(x)
    else:
        op.append(x)


def calculate(a, op, b):
    return str(eval(a+op+b))


def calculate_front(arr):
    result = arr[0]
    for i in range(1, len(arr)-1, 2):
        result = calculate(result, arr[i], arr[i+1])
    return result


def dfs(index, arr, is_used):
    global answer
    if index == len(op):
        answer = max(answer, int(calculate_front(arr)))
        return
    if is_used:
        temp = copy.deepcopy(arr)
        temp.append(op[index])
        temp.append(nums[index+1])
        dfs(index+1, temp, False)
    else:
        temp = copy.deepcopy(arr)
        temp.append(op[index])
        temp.append(nums[index+1])
        dfs(index+1, temp, False)
        temp.pop()
        temp.pop()
        temp.pop()
        temp.append(calculate(nums[index], op[index], nums[index+1]))
        dfs(index+1, temp, True)


answer = -MAX
dfs(0, [nums[0]], False)
print(answer)

 

백트랙킹

1. 입력을 받을 때, 숫자와 연산자를 따로 분리해서 넣어준다.

2. 하나의 식 계산 (calculate) : 해당 식을 계산해서 반환

3. 전체식을 앞에서부터 계산(calculate_front) : 앞에서부터 차근차근 계산한 값을 반환

4. dfs

    - index : 연산자의 인덱스값

    - arr : 현재의 식을 담은 리스트

    - is_used : 직전에 괄호를 사용했는지에 대한 여부 (직전에 사용했으면 다음 연산자에서는 사용불가)

    - index == 연산자리스트의 길이 이면, answer를 최댓값으로 업데이트

    - is_used == True 이면, 괄호 사용 불가

    - is_used == False 이면, 괄호 사용 or 괄호 사용X

5. answer 출력

 

13퍼에서 계속 틀렸습니다가 나오길래 뭐가 문제일까하고 다시 구르기 시작했다.

원인은 answer의 값을 0으로 해줬어서 최댓값이 음수일 때 0으로 출력...

오늘도 눈물이난다.