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

문제 해석

---

문제 풀이

---

문제 알고리즘 선택

• 중복된 괄호가 가능하며 괄호의 갯수 제한이 없다
• 모든 경우의 수를 계산하여도 수식의 길이가 19라 충분할 것처럼 보인다.
• 브루트포스로 풀이

풀이 과정

1. 숫자와 연산자를 분리하여 저장한다.
2. 연산자의 index를 기준으로 각각의 연산자가 먼저 계산되는 permutation을 구한다
3. 구한 값과 기존 식을 결합시킨다 (연산자의 경우 사용한 연산자를 제외시킨다)
4. 숫자 배열이 1개만 남았을 때 값을 정답배열에 추가시킨다
5. 정답 배열에서 값을 도출한다

 

코   드

---

import re
import sys
import operator
from itertools import permutations

length = int(sys.stdin.readline())
expression = sys.stdin.readline()
matcher = {'*': operator.mul, '+': operator.add, '-': operator.sub, '/': operator.floordiv}
digit = list(map(int, re.findall('\\d', expression)))
oper = list(re.findall('\\D', expression))[:-1]
answer = []


def calc(opd, opt):
    if len(opd) == 1:
        answer.append(opd)
        return

    for i in range(len(opt)):
        new_opd = opd[:i] + [matcher[opt[i]](opd[i], opd[i + 1])] + opd[i + 2:]
        new_opt = opt[:i] + opt[i + 1:]
        calc(new_opd, new_opt)
    return


calc(digit, oper)
print(max(answer)[0])

느낀점: 재귀 어렵다..

날짜: 2024.03.12 brute force

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

16639번: 괄호 추가하기 3