백준(BOJ) 16638번 괄호 추가하기 2

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

16638번: 괄호 추가하기 2

풀이 :

 

기존 괄호 추가하기 문제는 단순히 해당하는 괄호 연산 (A 연산자 B) 를 ( A 연산자 B + 0 ) 의 형태로 바꾸어서

 

계산해주었지만 곱셈 우선 계산 시  0 * 다음값이 되어 0이 나오므로 다른 방법이 필요하다.

 

따라서  여분의 배열을 하나더 만들어서 괄호 부분은 A연산자B만 담게 되고 연산자로 곱하기를 만나게 되면 여분의 배

 

열에 값과 계산해서 다시 넣어주는 형태로 작성하였다.

 

 

코드 ( C++ )

	#include <iostream>
	#include <string>
	#include <algorithm>
	#include <vector>
	using namespace std;
	int n;
	vector<int> v;
	int ans = -2147483648;
	void solve(int begin, vector<int> p, vector<int> cand, int cnt)
	{
	if (p.size() == cnt) {
	// 중복 괄호 제거
	for (int i = 0; i < p.size()-1; ++i) {
	if (p.size() == 0) break;
	if (p[i + 1] - p[i] == 2) return;
	}
	vector<int> cp(v);
	//괄호계산
	for (int i = 0; i < p.size(); ++i) {
	int x = p[i];
	if (cp[x] == 0) {
	cp[x - 1] += cp[x + 1];
	cp[x] = -1;
	cp[x + 1] = 0;
	}
	else if (cp[x] == 1) {
	cp[x - 1] -= cp[x + 1];
	cp[x] = -1;
	cp[x + 1] = 0;
	}
	else {
	cp[x - 1] *= cp[x + 1];
	cp[x] = -1;
	cp[x + 1] = 0;
	}
	}
	//곱하기계산
	vector<int> temp;
	for (int i = 0; i < cp.size(); ++i) {
	if (i % 2 == 0)
	temp.push_back(cp[i]);
	else {
	//괄호였다면 0이 추가 되므로 그냥 뛰어넘는다.
	if (cp[i] == -1) {
	i++;
	}
	else {
	//곱하기라면
	if (cp[i] == 2) {
	int num = temp.back() * cp[i + 1];
	temp.pop_back();
	temp.push_back(num);
	i++;
	}
	else {
	temp.push_back(cp[i]);
	}
	}
	}
	}
	//왼쪽부터계산
	int ret = temp[0];
	for (int i = 1; i < temp.size(); ++i) {
	if (i % 2 == 1) {
	if (temp[i] == 0) {
	ret += temp[i + 1];
	}
	else if (temp[i] == 1) {
	ret -= temp[i + 1];
	}
	else
	ret *= temp[i + 1];
	}
	}
	ans = max(ans, ret);
	return;
	}
	for (int i = begin + 1; i < cand.size(); ++i) {
	p.push_back(cand[i]);
	solve(i, p,cand, cnt);
	p.pop_back();
	}
	}
	int main() {
	cin >> n;
	v = vector<int>(n);
	string s;
	cin >> s;
	for (int i = 0; i < n; ++i) {
	if (i % 2 == 1) {
	if (s[i] == '+')
	v[i] = 0;
	else if (s[i] == '-')
	v[i] = 1;
	else
	v[i] = 2;
	}
	else
	v[i] = s[i] - '0';
	}
	vector<int> cp(v);
	vector<int> cand;
	for (int i = 0; i < n; ++i) {
	if (i % 2 == 1) cand.push_back(i);
	}
	vector<int> picked;
	for (int i = 0; i <= (n - 1) / 2; ++i) {
	solve(-1, picked, cand,i);
	}
	cout << ans << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub