Boj 16638) 괄호 추가하기 2

문제

백준 16638

설명

더 좋은 방법도 있겠지만, 그냥 괄호넣고 후위표기식으로 전환해서 풀었다. 말 그대로 시키는 대로 한 것.

시간 복잡도

O(\(2^10\mathrm{N}\))

• 주어진 수식의 길이인 19 에 괄호를 넣는 횟수를 계산하기가 좀 까다로웠다. 그래서 러프하게 각 숫자마다 괄호를 넣을지 말지 고려한다고 치고 계산했다.

코드

int n, ans = INT_MIN;
char infix[1000];

bool IsOP(char op)
{
	return op == '*' || op == '+' || op == '-';
}

bool IsBIG(char op, char op2)
{
	return op == '*' && op2 != '*';
}

string Postfix()
{
	string postfix;
	stack<char> st; st.push('.');
	for (int i = 0; i < n; i++)
	{
		char cur = infix[i];
		if ('0' <= cur && cur <= '9') postfix += cur;
		else if (cur == '(') st.push(cur);
		else if (cur == ')')
		{
			while (IsOP(st.top()))
			{
				postfix += st.top(); st.pop();
			}
			st.pop();
		}
		else
		{
            while (IsOP(st.top()) && !IsBIG(cur, st.top()))
			{
				postfix += st.top(); st.pop();
			}
            st.push(cur);
		}
	}
	while (IsOP(st.top())){ postfix += st.top(); st.pop();}

	return postfix;
}

int Evaluate(int& cur, string& postfix)
{
	char op = postfix[cur];
	cur--;
	if (!IsOP(op)) return op - '0';
	int rh = Evaluate(cur, postfix);
	int lh = Evaluate(cur, postfix);
	switch (op)
	{
	case '+': return lh + rh;
	case '-': return lh - rh;
	case '*': return lh * rh;
	}
}

void PAdd(int cur, int lh = 0, bool p = false)
{
	if (cur >= n)
	{
		string postfix = Postfix();
		int iter = postfix.size() - 1;
		ans = max(ans, Evaluate(iter, postfix));
		return;
	}

	PAdd(cur + 2);

	// (a+b)+c
	if (cur + 2 < n)
	{
		copy(infix + cur + 3, infix + n, infix + cur + 5); n += 2;
		copy(infix + cur, infix + cur + 3, infix + cur + 1);
		infix[cur] = '('; infix[cur + 4] = ')';
		PAdd(cur + 6);
		copy(infix + cur + 1, infix + cur + 4, infix + cur);
		copy(infix + cur + 5, infix + n, infix + cur + 3); n -= 2;
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> infix[i];
	PAdd(0);
	cout << ans;
}