[백준 16637] 괄호 추가하기 (C++)

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

 

문제

---

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

 

입력

---

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

 

출력

---

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 2³¹보다 작고, -2³¹보다 크다.

 

문제 풀이

---

브루트포스 문제.

 

만들 수 있는 모든 경우를 탐색한 후 그 중 값이 가장 큰 경우를 출력해주면 된다. 연산자의 개수만큼의 칸을 가진 boolean 타입의 배열을 선언하여 백트래킹을 이용하여 해결하였다. i번째 칸이 true라면 해당 연산자를 가지는 계산이 괄호를 가진다는 뜻으로 정의한다. 예릍 들면 3+5+2라는 수식에서 0번째 칸이 true라면 (3+5)이고, 1번째 index가 true라면 (5+2)라는 뜻이 된다. 괄호 안에는 연산자가 한 개 있어야 하므로 이전 index의 값이 true라면 현재 인덱스의 값은 false가 되어야 한다.

만들 수 있는 한 가지 경우의 수가 구해지면(=백트래킹 함수의 depth가 연산자의 개수일 때) 괄호에 따라 계산해주면 된다. 괄호가 있다면 해당 부분을 먼저 계산하고, 없다면 이전 계산을 이용하여 연산자에 맞는 연산을 해주면 된다.

 

아래는 코드.

#include <iostream>
#include <vector>
#include <climits>

using namespace std;
bool* hasParen;
string str;
int* operands;
int answer;

int calc(int prev, int current, char op)
{
	if (op == '+')
	{
		return prev + current;
	}
	if (op == '-')
	{
		return prev - current;
	}
	return prev * current;
}

void backTracking(int depth, int operatorSize)
{
	if (depth == operatorSize)
	{
		vector<int> v;
		int currentResult = calc(str.at(0)-48, str.at(2)-48, str.at(1));
		v.push_back(str.at(0) - 48);
		v.push_back(currentResult);
		for (int i=1;i<operatorSize;i++)
		{
			int originalOperatorIndex = i * 2 + 1;
			if (hasParen[i] == true)
			{
				int prev = str.at(originalOperatorIndex - 1) - 48;
				int current = str.at(originalOperatorIndex + 1) - 48;
				int currentResult = calc(prev, current, str.at(originalOperatorIndex));
				int calcResult = calc(v.at(v.size() - 2), currentResult, str.at(originalOperatorIndex - 2));
				v.push_back(calcResult);
			}
			else
			{
				int calcResult = calc(v.at(v.size() - 1), str.at(originalOperatorIndex + 1) - 48, str.at(originalOperatorIndex));
				v.push_back(calcResult);
			}
		}
		answer = max(answer, v.back());
	}
	else
	{
		if (depth==0 || (depth != 0 && hasParen[depth - 1] == false))
		{
			hasParen[depth] = true;
			backTracking(depth + 1, operatorSize);
		}
		hasParen[depth] = false;
		backTracking(depth + 1, operatorSize);
	}
}

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

	int N;
	cin >> N;
	cin >> str;
	if (N == 1)
	{
		cout << str << "\n";
	}
	else
	{
		int operandSIze = (N + 1) / 2;
		int operatorSize = N - operandSIze;
		hasParen = new bool[operatorSize];
		for (int i = 0; i < operatorSize; i++)
		{
			hasParen[i] = false;
		}
		answer = INT_MIN;
		backTracking(0, operatorSize);
		cout << answer << "\n";
	}
	return 0;
}