[백준][브루트포스] 괄호 추가하기

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

16637번: 괄호 추가하기

 

내가 작성한 코드

mx = -float('inf')

def read_data():
    N = int(input().rstrip())
    equation = input().rstrip()
    operand = []
    operation = []
    for i, v in enumerate(equation):
        if i % 2 == 0:
            operand.append(int(v))
        else:
            operation.append(v)

    return operation, operand

def op(a, b, x):
    if x == '+':
        return a+b
    elif x == '-':
        return a-b
    else:
        return a*b

def do(operand, operation, i):
    a, b, x = operand[i], operand[i+1], operation[i]
    v = op(a, b, x)

    operand.pop(i)
    operand.pop(i)
    operand.insert(i, v)
    operation.pop(i)

    return a, b, x

def undo(operand, operation, i, a, b, x):
    operand.pop(i)
    operand.insert(i, b)
    operand.insert(i, a)
    operation.insert(i, x)

def fin(operand, operation):
    global mx
    _operand, _operation = [], []
    for _ in range(len(operation)):
        a, b, x = do(operand, operation, 0)
        _operand.append(a)
        _operand.append(b)
        _operation.append(x)
    mx = max(mx, operand[0])
    for _ in range(len(_operation)):
        b = _operand.pop()
        a = _operand.pop()
        x = _operation.pop()
        undo(operand, operation, 0, a, b, x)

def get_mx(operand, operation, i):
    if len(operation) <= i:
        fin(operand, operation)
        return

    a, b, x = do(operand, operation, i)
    get_mx(operand, operation, i+1)
    undo(operand, operation, i, a, b, x)
    get_mx(operand, operation, i + 1)

operation, operand = read_data()
get_mx(operand, operation, 0)
print(mx)

• 괄호 중복 불가
  
  • 괄호를 함 / 안함
    - do, get_mx, undo / get_mx
  • 괄호를 하고 i+1
    - [1,2,3] / i = 0일 때 i와 i+1을 연산
    - [3,3] / i = 0에서 i+1이므로
    - 결국 2칸 건너뛰게되어 괄호를 할 수 있는 범위
  • 괄호를 안하고 i+1
    - 앞 숫자에 괄호를 하지 않았으므로 i+1부터 괄호 가능

 

다른 사람이 작성한 코드

None

• 다른 코드들도 비슷하게 구현
• DP로 풀었다는 코드를 봤는데
  
  • 오 하고 코드를 보는데 DP가 아닌 것 같았음 (memoization이 되지 않고 값을 모두 계산)
  • 괄호 조건을 만족하지 못했음 (혹시나해서 제출해봤는데 틀림)
  • 그러나 나는 DP로 하겠다는 접근을 못했음
  • 그 분처럼 DP 문제를 많이 풀어보고 접근해보는 자신감이 필요한 듯

 

기억해야할 것