[백준/BOJ] 백준 16637번 : 괄호 추가하기

www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

basket을 통해 괄호를 치는 것을 표현하여 괄호를 칠 수 있는 경우를 모두 확인하고 Calc를 통해 그때의 수식을 계산한다. Calc는 괄호가 쳐있는 위치가 아니라면 result1에 push 하고, 괄호가 쳐져 있는 위치라면 그 괄호 안의 수식을 계산하고 계산한 값을 result1에 push 하는 방법을 통해 괄호 안의 값을 우선적으로 계산한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <string>
#include <queue>
#include <cmath>
#include <map>
using namespace std;

int n;
string input;

int Oper(int number1, string oper, int number2)
{
	int result;
	if (oper == "+")
	{
		result = number1 + number2;
	}

	else if (oper == "-")
	{
		result = number1 - number2;
	}

	else if (oper == "*")
	{
		result = number1 * number2;
	}

	return result;
}

int Calc(vector<int>& basket)
{
	vector<string> result1;

	for (int i = 0; i < input.size();)
	{
		if (basket[i] == 1) //괄호 위치일때
		{
			int number1 = stoi(input.substr(i, 1));
			string oper = input.substr(i + 1, 1);
			int number2 = stoi(input.substr(i + 2, 1)); //다음 괄호 위치
			int temp_result = Oper(number1, oper, number2); //괄호안의 수식 계산

			result1.push_back(to_string(temp_result));
			i++;
			i++;
			i++;
		}

		else
		{
			result1.push_back(input.substr(i, 1));
			i++;
		}
	}

	vector<string> result2;
	result2.push_back("0");
	result2.push_back("+");
	int final_result;

	//순서대로 계산
	for (int i = 0; i < result1.size(); i++)
	{
		result2.push_back(result1[i]);

		if (result2.size() == 3)
		{
			int number1 = stoi(result2[0]);
			string oper = result2[1];
			int number2 = stoi(result2[2]);

			final_result = Oper(number1, oper, number2);

			result2.clear();
			result2.push_back(to_string(final_result));
		}
	}

	return final_result;
}

int Solve(vector<int>& basket, int can_basket)
{
	//괄호를 칠 수 있는 시작 위치가 n-1 이상일때 즉 더 이상 괄호를 칠 수 없을때 
	if (can_basket >= n - 1)
	{
		return Calc(basket);
	}

	int ret = Calc(basket); //더이상 괄호를 치지 않는것 계산

	for (int i = can_basket; i < n; i++)
	{
		if (input[i] >= '0' && input[i] <= '9' && i + 2 < n) //괄호를 칠 수 있는 위치일때
		{
			ret = max(ret, Solve(basket, i + 4)); //괄호를 안치고 넘어가는것
			basket[i] = 1;
			basket[i + 2] = 1;
			ret = max(ret, Solve(basket, i + 4)); //괄호를 치고 넘어가는것
			basket[i] = 0;
			basket[i + 2] = 0;
		}
	}


	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	cin >> input;

	vector<int> basket(n, 0);
	cout << Solve(basket, 0);

	return 0;
}