[백준] : 16637 괄호 추가하기 / python

1. 문제 설명

문제

16637번: 괄호 추가하기

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다.
연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다.
예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다.
단, 괄호 안에는 연산자가 하나만 들어 있어야 한다.
예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다.
하지만, 중첩된 괄호는 사용할 수 없다.
즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오.
추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

 

입력

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다.
수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다.
문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다.
연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다.
항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

 

출력

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 
정답은 2^31보다 작고, -2^31보다 크다.

 

2. 풀이 전 계획과 생각

입력

• N → 수식의 길이
• expression → (operand : 1-9 operator : *, + ,-)
  • operand, operator 분리해주자.

 

구하고자 하는 바

괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하기

 

행위의 규칙성, 패턴 파악

• 제한조건
  • 괄호 안에는 연산자가 하나만
  • 중첩된 괄호는 사용할 수 없다.

⇒ 해당 제한조건에 맞게 괄호를 추가해주는 모든 경우를 구하고 해당 괄호를 먼저 연산해주어야 한다.

 

필요한 로직

• 괄호를 적절히 추가하는 모든 경우를 구하는 함수
• 해당 괄호에 따라 연산하는 함수

 

3. 풀이

import re

MIN_INT = -(2 ** 31)
N = int(input())
expression = input()
selected_operators_idx = []

def part_calculate(operator, num1, num2):
    if operator == "*":
        return num1 * num2
    elif operator == "+":
        return num1 + num2
    elif operator == '-':
        return num1 - num2

def total_calculate():
    input_operators = re.split('[1-9]', expression)[1:-1]
    input_operands = re.split('[*+-]', expression)

    for idx in selected_operators_idx:
        part_result = part_calculate(input_operators[idx], int(input_operands[idx]), int(input_operands[idx + 1]))
        del input_operators[idx]
        del input_operands[idx + 1]
        input_operands[idx] = part_result

    while len(input_operands) > 1:
        idx = 0
        part_result = part_calculate(input_operators[idx], int(input_operands[idx]), int(input_operands[idx + 1]))
        del input_operators[idx]
        del input_operands[idx + 1]
        input_operands[idx] = part_result

    return input_operands[0]

def combination(current_idx):
    global answer
    if current_idx == N // 2:
        answer = max(answer, total_calculate())
        return

    selected_operators_idx.append(current_idx)
    combination(current_idx + 1)
    selected_operators_idx.pop()
    combination(current_idx + 1)

answer = MIN_INT
combination(0)

 

문제점

Indexing Error

연산자와 피연산자를 저장한 배열을 변경해주면, 미리 저장해준 ‘괄호로 선택한 연산자의 index’를 사용해줄 수가 없다.

왼쪽에서 오른쪽으로 계산하므로, 선택한 연산자를 먼저 계산하고 계산한 결과 + 0 으로 해준다.

 

4. 2차 풀이

import re

MIN_INT = -(2 ** 31) - 1
N = int(input())
expression = input()
selected_operators_idx = []

def part_calculate(operator, num1, num2):
    if operator == "*":
        return num1 * num2
    elif operator == "+":
        return num1 + num2
    elif operator == '-':
        return num1 - num2

def total_calculate():
    input_operators = re.split('[0-9]', expression)[1:-1]
    input_operands = re.split('[*+-]', expression)
    for idx in selected_operators_idx:
        part_result = part_calculate(input_operators[idx], int(input_operands[idx]), int(input_operands[idx + 1]))

        input_operators[idx] = "+"
        input_operands[idx + 1] = "0"
        input_operands[idx] = part_result

    while len(input_operands) > 1:
        idx = 0
        part_result = part_calculate(input_operators[idx], int(input_operands[idx]), int(input_operands[idx + 1]))
        del input_operators[idx]
        del input_operands[idx + 1]
        input_operands[idx] = part_result

    return input_operands[0]

def combination(current_idx):
    global answer
    if current_idx == N // 2:
        answer = max(answer, total_calculate())
        return

    selected_operators_idx.append(current_idx)
    combination(current_idx + 1)
    selected_operators_idx.pop()
    combination(current_idx + 1)

answer = MIN_INT
combination(0)
print(answer)

 

문제점

틀렸습니다.

0을 더해주면 0과 다음의 기존연산자가 *면 계산이 달라지는 결과가 생긴다.

 

5. 풀이하면서 막혔던 점과 고민

🤔 미리 저장해준 ‘괄호로 선택한 연산자의 index’를 사용해주면,  
      연산 결과를 입력받은 연산자와 피연산자 배열에 반영해줄 수가 없다.
     어떻게 해주면 좋을까?

→ 재귀함수를 호출할 때, 연산한 값을 바로 재귀함수에 반영하여 호출해준다.

 

6. 3차 풀이

import re

MIN_INT = -(2 ** 31) - 1
N = int(input())
expression = input()
operators = re.split('[0-9]', expression)[1:-1]
operands = re.split('[*+-]', expression)
operands = [int(element) for element in operands]

def calculate(num1, num2, operator):
    if operator == "*":
        return num1 * num2
    elif operator == "+":
        return num1 + num2
    elif operator == '-':
        return num1 - num2

def go(current_idx, value):
    global answer
    if current_idx == len(operands):
        answer = max(answer, value)
        return

    # 괄호 없이 계산한 경우
    go(current_idx + 1, calculate(value, operands[current_idx], operators[current_idx - 1]))
    # 괄호가 있는 경우
    if current_idx + 2 <= len(operands):
        go(current_idx + 2, calculate(value, calculate(operands[current_idx], operands[current_idx + 1], operators[current_idx]), operators[current_idx - 1]))

answer = MIN_INT
go(1, operands[0])
print(answer)

 

7. 풀이 후 알게된 개념과 소감

• 재귀함수 호출 할 때,
  갈 수 있는 경우를 먼저 정의해주고 그에 따라 처리하고 처리한 값을 반영하여 다음으로 가면,
  모든 경우를 다 따져줄 수 있다.
  
  보통 백트레킹 문제를 풀 때, 무조건적으로 경우를 다 선택하고 난 뒤에
  다 선택한 경우를 한꺼번에 처리해주려고 했다.
  ⇒ 이 경우 문제에 따라 처리가 한꺼번에 하기 불가능한 경우도 있었다.
  
  이 접근 외에도
  갈 수 있는 경우를 다 따져주고 그에 따라 처리하고 처리한 값을 반영하여 다음으로 가면
  종료되었을 때 처리해주면 복잡한 문제여도 쉽게 문제를 해결해줄 수 있다.
  ⇒ 그러므로, 문제가 복잡할수록 차근차근 갈 수 있는 경우를 찾고 그에 따라 처리해주자.