백준 16637번 괄호 추가하기

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

16637번: 괄호 추가하기

 

 

 

 

<접근방법>

괄호의 위치를 백트래킹으로 완전 탐색합니다.

이때, 괄호의 갯수도 유의해야 합니다.

괄호의 위치를 정한 후, 수식 계산을 해줍니다.

 

계산은 괄호 안을 모두 계산을 한다음, 전체 수식을 계산하였습니다.

 

 

<느낀 점>

접근과 설계가 많이 부족하다.

 

 

---

 

 

 

<코드>

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

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

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

int simul() {
	vector<string> v;

	int i = 0;
	while (1) {
		if (i >= n) break;

		string ts;
		if (visit[i]) {
			int tmp = cal(str[i] - '0', str[i + 2] - '0', str[i + 1]);
			ts = to_string(tmp);
			v.push_back(ts);
			i += 3;
		}
		else {
			ts = str[i];
			v.push_back(ts);
			i++;
		}
	}

	int tres = stoi(v[0]);
	for (int i = 1; i < v.size() - 1; i += 2) {
		tres = cal(tres, stoi(v[i+1]), v[i][0]);
	}

	return tres;
}

void dfs(int dep) {
	if (dep == tlim) {
		res = max(res, simul());
		return;
	}

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

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

	int num_cnt = n / 2 + 1;
	lim = num_cnt / 2;

	for (int i = 0; i <= lim; i++) {
		memset(visit, false, sizeof(visit));
		
		tlim = i;
		dfs(0);
	}
	cout << res << '\n';
	return 0;
}