[Algorithm] BaekJoon : 16637. 괄호 추가하기 by Python

[문제 바로가기] https://www.acmicpc.net/problem/16637

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은 홀수이다.

 

예제 입력

9
3+8*7-9*2

---

💡문제 풀이

비슷한 문제를 이전에 풀어봤음에도 문제를 잘못 읽고, 잘못 접근하여 엄청난 시간을 낭비했다...

※ 중첩된 괄호는 사용할 수 없다고 하였는데 뒤늦게 알아서 코드를 전면 수정했다.😩

 

문제는 완전탐색 + 재귀를 이용하여 풀었다.

 

먼저, 괄호가 사용이 가능한 경우를 살펴보았다.

3 + 8 x 7 - 9 x 2 케이스가 주어질 경우, 연산자는 총 4개이다.

 

괄호가 사용가능한 경우는
(3+8)x7-9x2 / 3+(8x7)-9x2 / 3+8x(7-9)x2 ... 등 다양한 경우가 있는데

중첩된 괄호는 사용할 수 없다는 조건으로 괄호를 사용한 계산(연산자) 다음에는 연달아서 괄호를 사용할 수 없다.
ex) ((3+8)x7)-9x2에서 '+'에서 괄호를 사용했기 때문에 바로 다음의 'x' 연산자에서는 괄호 사용이 불가능하다.

 

따라서, 4개의 연산자를 인덱스 1, 2, 3, 4로 나타냈을 때 가능한 경우를 표현하면

• 괄호사용 X(1) 
• 괄호 1개(4) : 1 / 2 / 3 / 4
• 괄호 2개(3) : 1, 3 / 1, 4 / 2, 4

위와같이 총 8개의 경우가 나온다.

 

어떠한 계산이 최대값인지 알 수 없기 때문에 완전탐색을 이용하였고 계산에서 연산자의 위치(인덱스)는 홀수라는 점(0부터 시작)과 괄호를 사용하는/안하는 상황을 표현해야 하기 때문에 재귀를 사용하였다.

 

step 1)
먼저 주어진 계산식에서 숫자와, 연산자를 분리하였다.
이 때 숫자는 계산을 위해 정수(int)형태로 변경하였다.

 

• orders : 숫자, 연산자를 하나의 원소로 분리한 배열

 

step 2)
재귀 깊이는 연산자의 개수이기 때문에 count라는 변수에 따로 담아두었다.

 

• count : 연산자 수

재귀를 이용하여 괄호를 사용하는 경우 미리 연산을 진행한다.

• move 함수 : 괄호 사용여부를 파악하는 재귀 함수
• calculate 함수 : +, -, x 연산을 하는 함수

move 함수의 인자는 idx, cnt, flag, orders이다.

 

1. idx : 연산자의 위치
괄호를 사용하지 않을 경우 다음 연산자로 이동하기 위해 idx+2를 해준다.
하지만, 괄호를 사용하는 경우 숫자 2개와 연산자 1개가 숫자 하나로 변경되기 때문에

idx에 +2를 하지 않고 그대로 넣었다. (배열 길이가 -2가 된다.)
ex) 3, '+', 8(원소 3개) → 11(원소1개)

 

2. cnt : 연산자탐색 개수
재귀가 종료되는 경우는 모든 연산자를 다 탐색했을 경우다.
따라서, 괄호를 사용하든, 사용하지않든 재귀가 진행될때마다 cnt+1을 해주어 앞서 선언한 count(연산자 총 개수)와 비교했을 때 같으면 재귀를 종료한다.

 

3. flag : 괄호 사용 여부
중첩된 괄호는 사용할 수 없기 때문에 이전에 괄호를 사용했으면 다음 연산에서는 사용하면 안 된다.
이를 표현하기 위해 flag에 Boolean값을 주어 판별하였다.

 

만약 이전에 괄호를 사용했으면? 다음에는 무조건 괄호를 사용하면 안 된다.

하지만 이전에 괄호를 사용하지 않았으면? 다음에는 사용하거나 사용하지 않아도 된다.

 

• orders : 연산이 진행되는 배열
• 재귀가 진행되면서 변하는 배열이다.

move, calculate 함수를 통해 괄호가 사용되는 경우 연산이 진행이되며 괄호를 사용하지 않아서 남아있는 원소들은 candidates 배열에 담았다.

• candidates : 괄호를 사용하지 않아서 남은 원소들

step 3)
괄호를 사용하지 않고 남은 연산들은 candidates에 담겨져있다.
따라서, candidates에 담겨져 있는 연산들은 순서대로 진행하면 된다.

 

논리대로 앞의 원소들을 pop한 후 계산한 값을 가장 앞에 insert하면 좋지만 배열 특성상 원소의 이동으로 시간복잡도가 증가하기 때문에 슬라이싱([::-1])을 이용하여 뒤에서부터 계산하였다.

 

계산이 완료되면 answer와 비교하여 큰 값으로 answer를 최신화한다.
※ 연산의 결과로 최대값이 음수일 수도 있기 때문에 answer 초기값을 -0xffffff(큰 음수 값) 로 두었다.

 

코드는 다음과 같다.

 

def calculate(num1, order, num2): # '+', '-', 'x'을 연산하는 함수
    if order == '+':
        return num1 + num2
    elif order == '-':
        return num1 - num2
    else:
        return num1 * num2

def move(idx, cnt, flag, orders): # 괄호 사용 여부를 판별하는 함수
    global count
    if cnt == count: # 연산자 수 만큼 탐색을 완료했으면
        candidates.append(orders) # 남은 연산들이 담긴 orders는 candidates에 담는다.
        return
    if flag: # 이전에 괄호를 사용했으면 다음에는 무조건 사용X
        move(idx+2, cnt+1, False, orders) 
    else: # 이전에 괄호를 사용하지 않았으면 두 가지 경우가 존재한다.
        move(idx, cnt+1, True, orders[:idx-1] + [calculate(orders[idx-1], orders[idx], orders[idx+1])] + orders[idx+2:]) # 1. 괄호를 사용하는 경우 (해당 연산을 미리 계산한다.)
        move(idx+2, cnt+1, False, orders) # 2. 다음에도 사용하지 않는 경우

order = ['+', '-', '*']
N = int(input())
origin = input()
answer = -0xfffffff
orders = []
candidates = []

num = ''
for unit in origin: # 주어진 계산식(input)을 숫자, 연산자로 분리한다.
    if unit not in order:
        num += unit
    else:
        orders.append(int(num))
        orders.append(unit)
        num = ''
orders.append(int(num))

count = len(orders)//2
move(1, 0, False, orders)

for candidate in candidates:
    target = candidate[::-1]
    for i in range(len(candidate)//2):
        target.append(calculate(target.pop(), target.pop(), target.pop()))
    answer = max(answer, target[0])
print(answer)