[BOJ] 16637 : 괄호 추가하기 - travelbeeee

문제 : https://www.acmicpc.net/problem/16637

---

[ 알고리즘풀이 ]

■ 우리는 (N / 2) 개의 연산과 (N / 2) + 1 개의 숫자로 이루어진 식을 입력받는다. 또, 1, 3, 5, 7 ⋯ 과 같이 홀수 인덱스는 연산, 짝수 인덱스는 숫자에 해당한다.

■ N / 2 개의 연산 중 어느 곳에 괄호를 칠지 Backtracking 을 통해 모든 경우에 대해서 식을 계산해본다.

( 이때, 괄호를 친 연산 바로 다음 연산은 괄호가 겹치므로 괄호를 check 하면 안된다. )

■ 식을 앞에서부터 순회하며 괄호 유무에 따라 식을 숫자 파트와 연산 파트로 나눠서 vector 에 저장한다.

- 숫자와 숫자 다음 칸인 연산에 괄호가 쳐져있다면 그 다음 숫자와 먼저 계산을 하고 계산한 값과 그 다음 연산을 vector에 저장한다.

- 그렇지 않다면, 해당 숫자과 연산을 각각 vector에 저장한다.

■ 저장된 숫자와 연산을 계산한다.

■ 답을 갱신한다.

■ 답은 최대 9^10 으로 long long 으로 저장해줘야한다..!!!

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

int N;
long long ans = -999999999999999;
string expression;
bool op[9] = {};

long long getResult(void) {
	vector<long long> v1;
	vector<char> v2;
	int i = 0;
	while(i < N){
		if (op[(i + 1) / 2]) {// 숫잔데 괄호쳐져있음.
			if (expression[i + 1] == '+')
				v1.push_back((expression[i] - '0') + (expression[i + 2] - '0'));
			else if (expression[i + 1] == '-')
				v1.push_back((expression[i] - '0') - (expression[i + 2] - '0'));
			else if (expression[i + 1] == '*')
				v1.push_back((expression[i] - '0') * (expression[i + 2] - '0'));

			if (i + 3 < N)
				v2.push_back(expression[i + 3]);
			i += 4;
		}
		else if (!op[(i + 1) / 2]){
			v1.push_back(expression[i] - '0');
			if(i + 1 < N)
				v2.push_back(expression[i + 1]);
			i += 2;
		}
	}
	long long sum = v1[0];
	for (int i = 1; i < v1.size(); i++) {
		if (v2[i - 1] == '+')
			sum += v1[i];
		else if (v2[i - 1] == '-')
			sum -= v1[i];
		else if (v2[i - 1] == '*')
			sum *= v1[i];
	}
	return sum;
}

void Backtracking(int start) {
	ans = max(ans, getResult());
	for (int i = start; i < N / 2; i++) {
		op[i] = 1;
		Backtracking(i + 2);
		op[i] = 0;
	}
	return;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> expression;

	Backtracking(0);

	cout << ans;
}

---