괄호 추가하기 (16637)

1. 문제 링크

문제 링크

2. 풀이

백트래킹을 이용해 괄호를 치는 모든 경우의 수를 다 만들어본 후,
수식을 계산해서 최댓값을 출력하면 되는 문제입니다.

1. 괄호 치기

예제 2번의 수식인 8*3+5+2를 예로 문제를 설계해봅시다.
일단 n에 대해서 숫자의 개수와 연산자의 개수는 어떻게 정의될까요?

• 연산자의 개수: n / 2
• 숫자의 개수: n - 연산자의 개수

로 쉽게 알아낼 수 있습니다.
괄호를 칠 수 있는 부분은 숫자의 왼쪽, 오른쪽에 칠 수 있으니,
괄호의 개수는 숫자의 개수 * 2 가 됩니다.

이제 수식을 배열에 나열해보겠습니다.

규칙이 보이시나요?
홀수 인덱스는 수식이 들어가고
짝수 인덱스는 괄호가 들어갑니다.
짝수 인덱스에서 더 규칙을 찾아보면
인덱스 / 2가 짝수면 여는 괄호, 홀수면 닫는 괄호를 넣는 부분이란 걸 알 수 있습니다.
이제 백트래킹을 이용해 짝수 인덱스에 괄호를 넣어주면 됩니다.

2. 수식 계산하기

// 스택에 쌓인 숫자와 연산자에 따라 값을 계산
int calcFormula(int num) {
	int oper = st.top();
	st.pop();

	int otherNum = st.top();
	st.pop();

	if (oper == PLUS) {
		otherNum += num;
	}
	else if (oper == MINUS) {
		otherNum -= num;
	}
	else {
		otherNum *= num;
	}

	return otherNum;
}

// 수식을 순회하면서 수식의 값에 따라 스택에 넣으며 계산하기
for (int i = 0; i < len; i++) {
	// 빈 값일 때
	if (numEx[i] == EMPTY) continue;

	// 열린 괄호거나 연산자일 때
	if (numEx[i] == OPEN || numEx[i] == PLUS || numEx[i] == MINUS || numEx[i] == MULT) {
		st.push(numEx[i]);
		continue;
	}

	// 닫는 괄호일 때
	if (numEx[i] == CLOSE) {
		int num = st.top();

		st.pop();
		st.pop();

		if (!st.empty()) {
			num = calcFormula(num);
		}

		st.push(num);
		continue;
	}

	// 비어있거나 여는 괄호가 위에 있을 때
	if (st.empty() || st.top() == OPEN) {
		st.push(numEx[i]);
		continue;
	}

	// 안 비어있고 숫자일 때
	st.push(calcFormula(numEx[i]));
}

int ret = st.top();

st.pop();

스택을 이용해서 구현했습니다.
예시 하나만 해보겠습니다.
괄호가 8*(3+5)+2 이렇게 쳐져있다고 가정하겠습니다.

첫 번째 수식: 8
스택이 비어있으니 스택에 넣습니다. [8]

두 번째 수식: *
연산자이니 스택에 넣습니다. [8, *]

세 번째 수식: (
여는 괄호이니 스택에 넣습니다. [8, *, (]

네 번째 수식: 3
여는 괄호가 위에 있으니 스택에 넣습니다. [8, *, (, 3]

다섯 번째 수식: +
연산자이니 스택에 넣습니다. [8, *, (, 3, +]

여섯 번째 수식: 5
안 비어있고 숫자이니 스택에서 차례대로 pop해서
연산자인 +와 그 이전 숫자인 3과 현재 숫자인 5를 이용해 계산한 뒤에
그 결과인 8을 스택에 넣습니다. [8, *, (, 8]

일곱 번째 수식: )
닫는 괄호이면 스택에서 한 번 pop해서 계산한 결과를 들고 있고
다시 한 번 pop해서 여는 괄호를 제거합니다.
그리고 다시 스택에 넣을 때 스택이 비어있지 않다면
여섯 번째 수식때처럼 스택에서 차례대로 pop해서
연산자인 *와 그 이전 숫자인 8과 현재 들고 있는 숫자인 8을 이용해 계산한 뒤에
그 결과인 64를 스택에 넣습니다. [64]

여덟 번째 수식: +
연산지이니 스택에 넣습니다. [64, +]

아홉 번째 수식: 2
비어있지 않고 숫자이니 스택에서 차례대로 pop해서
연산자인 +와 그 이전 숫자인 64와 현재 숫자인 2를 이용해 계산한 뒤에
그 결과인 66을 스택에 넣습니다. [66]

이로써 모든 과정이 끝났습니다.
결과적으로 스택엔 숫자 하나만 남고, 그 숫자가 계산 결과가 됩니다.

3. 전체 코드

#define MAX 19
#define EMPTY -1
#define PLUS -2
#define MINUS -3
#define MULT -4
#define OPEN -5
#define CLOSE -6
#include <bits/stdc++.h>

using namespace std;

int n, len, bracketCount;
int numEx[MAX + MAX / 2 * 2 + 2];
stack<int> st;

// 스택에 쌓인 숫자와 연산자에 따라 값을 계산
int calcFormula(int num) {
	int oper = st.top();
	st.pop();

	int otherNum = st.top();
	st.pop();

	if (oper == PLUS) {
		otherNum += num;
	}
	else if (oper == MINUS) {
		otherNum -= num;
	}
	else {
		otherNum *= num;
	}

	return otherNum;
}

int slove(int depth) {
	if (depth >= bracketCount) {
		// 수식을 순회하면서 수식의 값에 따라 스택에 넣으며 계산하기
		for (int i = 0; i < len; i++) {
			// 빈 값일 때
			if (numEx[i] == EMPTY) continue;

			// 열린 괄호거나 연산자일 때
			if (numEx[i] == OPEN || numEx[i] == PLUS || numEx[i] == MINUS || numEx[i] == MULT) {
				st.push(numEx[i]);
				continue;
			}

			// 닫는 괄호일 때
			if (numEx[i] == CLOSE) {
				int num = st.top();

				st.pop();
				st.pop();

				if (!st.empty()) {
					num = calcFormula(num);
				}

				st.push(num);
				continue;
			}

			// 비어있거나 여는 괄호가 위에 있을 때
			if (st.empty() || st.top() == OPEN) {
				st.push(numEx[i]);
				continue;
			}

			// 안 비어있고 숫자일 때
			st.push(calcFormula(numEx[i]));
		}

		int ret = st.top();

		st.pop();

		return ret;
	}

	// 괄호 안치고 넘어가기
	int ret = slove(depth + 2);

	// 괄호를 칠 수 있을 때 괄호 치기
	if ((depth + 3) * 2 < len) {
		numEx[depth * 2] = OPEN;
		numEx[(depth + 3) * 2] = CLOSE;
		ret = max(ret, slove(depth + 4));
		numEx[(depth + 3) * 2] = EMPTY;
		numEx[depth * 2] = EMPTY;
	}

	return ret;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	bracketCount = (n - n / 2) * 2;
	len = n + bracketCount;

	for (int i = 0; i < len; i++) numEx[i] = EMPTY;

	int s = 1;

	for (int i = 0; i < n; i++) {
		char c;
		int convert;

		cin >> c;

		if (c == '+') {
			convert = PLUS;
		}
		else if (c == '-') {
			convert = MINUS;
		}
		else if (c == '*') {
			convert = MULT;
		}
		else {
			convert = c - '0';
		}

		// 홀수 인덱스에 수식 넣기
		numEx[s] = convert;
		s += 2;
	}

	cout << slove(0);

	return 0;
}