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

www.acmicpc.net/problem/16638

16638번: 괄호 추가하기 2

basket에 체크하며 괄호를 칠 수 있는 경우를 모두 확인하고, 수식의 계산은 괄호 부분, 곱하기 부분, 남은 부분 순서로 계산을 하는데, 우선 괄호 부분 계산은 괄호의 범위가 아닌 것들은 result1에 넣고 괄호의 범위인것들은 계산을 하여 result1에 넣었다. 그리고 곱하기 부분 계산은 곱하기가 아닌 부분은 result2에 넣고 곱하기를 만나면 result2의 마지막 수와 곱하기 다음 수를 곱하여 기존 result2의 마지막 수를 뺴내고, 계산된 수를 result2에 푸쉬하여 곱하기를 우선 계산하였고, 남은 것은 곱하기가 없기 때문에 순서대로 계산했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
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;
	for (int i = 0; i < result1.size();)
	{
		if (result1[i] == "*")
		{
			int number1 = stoi(result2[result2.size() - 1]); //result2의 마지막 수
			string oper = result1[i];
			int number2 = stoi(result1[i + 1]);
			int temp_result = Oper(number1, oper, number2);

			result2.pop_back();
			result2.push_back(to_string(temp_result));
			i++;
			i++;
		}

		else
		{
			result2.push_back(result1[i]);
			i++;
		}
	}

	//곱하기가 없기 때문에 순서대로 계산
	vector<string> result3;
	result3.push_back("0");
	result3.push_back("+");
	int final_result;
	for (int i = 0; i < result2.size(); i++)
	{
		result3.push_back(result2[i]);

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

			final_result = Oper(number1, oper, number2);

			result3.clear();
			result3.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;
}