[백준/Python] 16637번 괄호 추가하기 풀이

문제 해석

---

문제 풀이

---

문제 알고리즘 선택

• 중첩된 괄호는 사용할 수 없고, 괄호의 갯수는 제한이 없다
• 괄호는 (a+b)+c 형식이거나 a+(b+c)의 형태로 3개의 숫자 중 12번을 묶거나 23번을 묶는 경우의 수만 존재한다.
• 재귀함수를 이용해 두 형태로 가지 뻗어 브루트포스로 풀어내기

풀이 과정

1. 식에서 숫자와 연산자를 분리하여 저장한다.
2. 숫자의 맨 앞 값을 빼내 연산자와 갯수를 맞춰준다.
3. index 숫자를 기준으로 재귀함수를 작성한다.
4. 괄호를 12번을 묶는 경우와 13번을 묶는 경우로 하여 계산한다.
5. index가 끝에 도달하면 정답 배열에 값을 추가한다.
6. 정답 배열의 최대값을 도출한다.

 

코   드

---

import sys
import operator
import re

s_length = int(sys.stdin.readline())
expression = sys.stdin.readline()

func = {'*': operator.mul, '+': operator.add, '/': operator.mul, '-': operator.sub}
opd = list(map(int, re.findall("\\d", expression)))
opt = re.findall("\\D", expression)[:-1]
sp = opd.pop(0)
answer = []


def find(idx, val):
    if idx >= len(opt):
        answer.append(val)
        return

    find(idx + 1, func[opt[idx]](val, opd[idx]))
    if idx + 2 <= len(opt):
        find(idx + 2, func[opt[idx]](val, func[opt[idx + 1]](opd[idx], opd[idx + 1])))
    return


find(0, sp)
print(max(answer))

느낀점: 사실 중첩된 괄호 사용불가를 보지 못해서 괄호 추가하기 3를 풀어버렸다... 문제를 잘 읽어야겠다. 그리고 생각보다 재귀 기준을 만드는 것도 어려운 문제였다.

날짜: 2024.03.11 brute force

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

16637번: 괄호 추가하기