[문제 바로가기] https://www.acmicpc.net/problem/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은 홀수이다.
💡 문제 풀이
비슷한 문제를 이전에 풀어봤음에도 문제를 잘못 읽고, 잘못 접근하여 엄청난 시간을 낭비했다...
※ 중첩된 괄호는 사용할 수 없다고 하였는데 뒤늦게 알아서 코드를 전면 수정했다.😩
문제는 완전탐색 + 재귀를 이용하여 풀었다.
먼저, 괄호가 사용이 가능한 경우를 살펴보았다.
3+8x7-9x2 케이스가 주어질 경우, 연산자는 총 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 / 2 / 3 / 4
- 괄호 2개 : 1, 3 / 1, 4 / 2, 4
위와같이 총 8개의 경우가 나온다.
어떠한 계산이 최대값인지 알 수 없기 때문에 완전탐색을 이용하였고 계산에서 연산자의 위치(인덱스)는 홀수라는 점(0부터 시작)과 괄호를 사용하는/안하는 상황을 표현해야 하기 때문에 재귀를 사용하였다.
step 1)
먼저 주어진 계산식에서 숫자와, 연산자를 분리하였다.
이 때 숫자는 계산을 위해 정수(int)형태로 변경하였다.
- orders : 숫자, 연산자를 하나의 원소로 분리한 배열
step 2)
재귀 깊이는 연산자의 개수이기 때문에 count라는 변수에 따로 담아두었다.
- count : 연산자 수
재귀를 이용하여 괄호를 사용하는 경우 미리 연산을 진행한다.
- move 함수 : 괄호 사용여부를 파악하는 재귀 함수
- calculate 함수 : +, -, x 연산을 하는 함수
move 함수의 인자는 idx, cnt, flag, orders이다.
idx : 연산자의 위치
괄호를 사용하지 않을 경우 다음 연산자로 이동하기 위해 idx+2를 해준다.
하지만, 괄호를 사용하는 경우 숫자 2개와 연산자 1개가 숫자 하나로 변경되기 때문에 idx에 +2를 하지 않고 그대로 넣었다. (배열 길이가 -2가 된다.)
ex) 3, '+', 8(원소 3개) → 11(원소1개)
cnt : 연산자탐색 개수
재귀가 종료되는 경우는 모든 연산자를 다 탐색했을 경우다.
따라서, 괄호를 사용하든, 사용하지않든 재귀가 진행될때마다 cnt+1을 해주어 앞서 선언한 count(연산자 총 개수)와 비교했을 때 같으면 재귀를 종료한다.
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)
