백준 16638번 괄호 추가하기2

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

16638번: 괄호 추가하기 2

 

 

 

 

 

<접근방법>

괄호가 가장 우선순위입니다. 그 다음으로 곱셈이 나머지 연산보다 우선순위입니다.

단순히 생각한대로 구현하기만 하면 되는 문제이지만 구현 디테일이 조금 까다로웠던 문제입니다.

 

저는 괄호만 일괄적으로 계산, 곱셈만 일괄적으로 계산, 나머지 계산하는 순서로 풀었습니다.

 

<느낀 점>

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <limits.h>
#include <memory.h>
using namespace std;

int n, lim, res = INT_MIN;
bool visit[20];
string str;

int cal(int a, int b, char c) {
	int x = 0;
	switch (c) {
	case '*': x = a * b; break;
	case '+': x = a + b; break;
	case '-': x = a - b; break;
	}
	return x;
}

void simul3(vector<string> v) {
	int sum;
	string a;

	a = v[0];
	sum = stoi(a);
	for (int i = 1; i < (int)v.size(); i += 2) {
		sum = cal(stoi(a), stoi(v[i+1]), v[i][0]);
		a = to_string(sum);
	}
	res = max(res, sum);
}

void simul2(vector<string> v) {
	vector<string> s;
	string a;
	a = v[0];
	s.push_back(a);
	for (int i = 1; i < (int)v.size(); i += 2) {
		if (v[i][0] == '*') {
			string a = s.back();
			s.pop_back();
			s.push_back(to_string(cal(stoi(a), stoi(v[i+1]), '*')));
		}
		else {
			string a, b;
			a = v[i];
			s.push_back(a);

			b = v[i + 1];
			s.push_back(b);
		}
	}

	simul3(s);
}

 void simul1() {
	 vector<string> s;
	 string a;
	 a.push_back(str[0]);
	 s.push_back(a);
	for (int i = 1; i < n; i += 2) {
		if (visit[i]) {
			s.pop_back();
			s.push_back(to_string(cal(str[i-1] - '0', str[i+1] - '0', str[i])));
		}
		else {
			string a, b;
			a.push_back(str[i]);
			s.push_back(a);

			b.push_back(str[i + 1]);
			s.push_back(b);
		}
	}

	simul2(s);

}

void dfs(int dep, int start) {
	if (dep == lim) {
		simul1();
		return;
	}

	for (int i = start; i < n; i ++) {
		if (i % 2 == 0) continue;
		if (visit[i]) continue;
		if (i-2 >= 0 && visit[i-2]) continue;
		
		visit[i] = true;
		dfs(dep + 1, i + 1);
		visit[i] = false;
	}
}

int main() {
	cin >> n >> str;

	int sz = n / 2;
	for (int i = 0; i <= sz; i++) {
		memset(visit, false, sizeof(visit));
		lim = i;

		dfs(0, 0);
	}
	cout << res << '\n';
	return 0;
}