[16637번] 괄호 추가하기

16637번: 괄호 추가하기

 

www.acmicpc.net

 

완전 탐색 문제로 연산자별로 우선순위가 없기 때문에

괄호를 추가한다 --> 연산자 우선순위를 정한다 라고 생각하고 풀면 된다.

풀이 방법은

1. 괄호의 개수를 선택

2. 괄호로 묶을 연산자를 선택

3. 괄호로 묶은 연산자 들에게 우선순위 부여 ( 앞에서 부터 순서대로 묶어 보기 때문에 순서에 의한 우선순위는 걱정하지 않아도 됨)

4. 정해진 연산자 우선순위를 통해 stack을 후위 표기식 계산

5. 최대값 갱신

 

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <limits.h>
using namespace std;
int N, ans = INT_MIN;
string input;
vector<int>oper;
int chk[10];

int cal() {
	int result = 0;
	stack<int>num;
	stack<int>op;
	for (int i = 0; i < input.size(); i++) {
		if (i % 2 == 0) 
			num.push(input[i] - '0');
		else {
			if (op.empty()) op.push(i);
			else if (chk[op.top() / 2] > chk[i / 2]) op.push(i);
			else {
				while (chk[op.top() / 2] <= chk[i / 2]) {
					int tmp1 = num.top();
					num.pop();
					int tmp2 = num.top();
					num.pop();
					switch (input[op.top()]) {
					case '*':
						num.push(tmp1*tmp2);
						break;
					case '+':
						num.push(tmp1 + tmp2);
						break;
					case '-':
						num.push(tmp2 - tmp1);
						break;
					}
					op.pop();
					if (op.empty()) break;
				}
				op.push(i);
			}
		}
	}
	while (!op.empty()) {
		int tmp1 = num.top();
		num.pop();
		int tmp2 = num.top();
		num.pop();
		char c = input[op.top()];
		switch (c) {
		case '*':
			num.push(tmp1*tmp2);
			break;
		case '+':
			num.push(tmp1 + tmp2);
			break;
		case '-':
			num.push(tmp2 - tmp1);
			break;
		}
		op.pop();
	}
	result = num.top();
	return result;
}

void selop(int dep, int cnt,int idx) {
	if (dep == cnt) {
		int res = cal();
		ans = ans < res ? res : ans;
		/*for (int i = 0; i < oper.size(); i++)
			cout << chk[i] << ' ';
		cout << '\n';*/
		return;
	}
	else {
		for (int i = idx; i < oper.size(); i++) {
			if (chk[i] != 100)continue;
			if (dep == 1) {
				chk[i] = dep;
				selop(dep + 1, cnt, i + 1);
				chk[i] = 100;
			}
			else {
				if (chk[i - 1] == 100) {
					chk[i] = dep;
					selop(dep + 1, cnt, i + 1);
					chk[i] = 100;
				}
				else continue;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	cin >> input;
	int priority = 1;
	for (int i = 0; i < input.size(); i++) {
		if (input[i]<'0' || input[i] >'9')
			oper.push_back(priority++);
	}
	for (int i = 0; i < oper.size(); i++)
		chk[i] = 100;
	for (int i = 1; i <= (N + 1) / 2; i++)
		selop(1, i, 0);
	cout << ans;
	return 0;
}