백준 - 16637번 : 괄호 추가하기 (C++)

풀이 방법 : 브루트 포스

문제에서 연산자의 우선순위는 괄호가 없다면 모두 동일하다고 가정했기 때문에 단순하게 괄호의 유무에 따른 경우들만 따져주면 된다.

처음 인덱스부터 시작해서 괄호 씌운 경우, 괄호 안씌운 경우로 나뉘어서 계산해준다.

씌우지 않은 경우는 그대로 인덱스만 증가시켜서 재귀함수에 넘겨준다.

씌운 경우에는 미리 계산을 해서 새로운 벡터 컨테이너에 넣어서 재귀함수에 넘겨준다.

인덱스가 마지막에 도달하게 된다면 최종적으로 앞에서부터 계산해준 후에 최댓값을 갱신해준다.

#include <iostream>
#include <vector>
#include <string>
#include <limits.h>

using namespace std;

int Max = INT_MIN;

bool check[11] = {};

void DFS(vector<int> vecNum, vector<char> vecOper, int Idx)
{
	int Size = (int)vecOper.size();

	//최종 계산
	if (Idx >= Size)
	{
		int Result = vecNum[0];

		for (int i = 0; i < Size; ++i)
		{
			int Dest = vecNum[i + 1];
			char Oper = vecOper[i];

			if (Oper == '+')
				Result += Dest;

			else if (Oper == '-')
				Result -= Dest;

			else
				Result *= Dest;
		}

		Max = max(Result, Max);
		return;
	}

	
	vector<int> NextNums = vecNum;
	vector<char> NextOper = vecOper;

	int Src = vecNum[Idx];
	int Dest = vecNum[Idx + 1];
	char Oper = vecOper[Idx];

	int Result = 0;

	if (Oper == '+')
		Result = Src + Dest;

	else if (Oper == '-')
		Result = Src - Dest;

	else
		Result = Src * Dest;

	auto iter = NextNums.begin() + Idx + 1;
	auto OperIter = NextOper.begin() + Idx;

	NextNums[Idx] = Result;
	NextNums.erase(iter);
	NextOper.erase(OperIter);
    
	DFS(vecNum, vecOper, Idx + 1); //괄호 안씌울 경우
	DFS(NextNums, NextOper, Idx + 1); //괄호 씌울 경우
		
}

int main()
{
	int N;
	cin >> N;

	string Formula;
	cin >> Formula;

	if (N == 1)
	{
		cout << Formula;
		return 0;
	}

	vector<int> vecNums;
	vector<char> vecOper;

	for (int i = 0; i < N; ++i)
	{
		if (i % 2 == 0)
			vecNums.push_back((int)Formula[i] - 48);

		else
			vecOper.push_back(Formula[i]);
	}

	DFS(vecNums, vecOper, 0);

	cout << Max;

}

어떤 경우에 분기점이 생기는지 잘 파악하자..