백준 16637번 괄호 추가하기 (c++)

 

일반적인 연산자 우선순위를 가졌거나 괄호의 중복이 가능하거나 하나의 괄호에 두개 이상의 연산자가 포함될 수 있었다면 매우매우 어려운 문제가 되었겠지만 단순한 연산조건으로인해 브루트포스하기 좋은 문제가 되었다.

 

기본적인 아이디어는 연산자의 위치마다 괄호를 쓴 상태와 쓰지 않은 상태를 전부 재귀함수로 돌려버리면 된다.

 

signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	cin >> s;
	q.push('+');
	for (char a : s)
	{	
		q.push(a);
	}
	sol(0, q);

	cout << ans << endl;
}

 

일단 받은 수식을 전부 분리해서 큐에 넣어준다. 앞에서 하나씩 꺼내 쓸 것이다.

 

큐에 +를 먼저 넣어준 이유는 재귀함수를 돌릴때 첫번째 루프에서의 예외를 없에기 위함이다.

설계 특성상 항상 연산자 위치에서 분기가 일어나는데 첫번째 재귀에서는 맨 앞에 연산자가 아니라 숫자가 오기 때문이다.

재귀함수를 0으로 시작하고 연산자 +를 삽입해준다면 값의 변화없이 처리할 수 있다

 

int n;
string s;
queue<char> q;
ll ans = -22222222222;

ll calc(ll num1, char op, ll num2)
{
	switch (op)
	{
	case '+':
		return num1 + num2;
		break;
	case '-':
		return num1 - num2;
		break;
	case '*':
		return num1 * num2;
		break;
	}
}

void sol(ll num, queue<char> exp)
{
	if (exp.empty())
	{
		ans = max(ans, num);
		return;
	}

	char op1 = exp.front(); exp.pop();
	ll num1 = exp.front() - '0'; exp.pop();
	sol(calc(num, op1, num1), exp);
	if (exp.empty()) return;

	char op2 = exp.front(); exp.pop();
	ll num2 = exp.front() - '0'; exp.pop();
	ll tmp = calc(num1, op2, num2);
	sol(calc(num, op1, tmp), exp);
}

 

계산의 편의성을 위해 두 숫자와 연산자를 받아 계산해주는 calc함수를 분리해 주었다.

재귀함수는 큐를 통째로 받아 상태를 갱신한다.

 

먼저 연산자1을 pop 하고, 숫자 하나를 pop 한다

 

'이어져 온 값 + 현재 값'

이상태로 매개변수로 받아온 num과 연산해서 재귀를 돌리면 괄호를 사용하지 않고 이번 턴을 넘긴 것이다.

 

이어서 연산자2를 pop 하고 숫자 하나를 더 pop 한다.

이번 재귀에서 pop한 숫자 두개를 연산자 2와 연산한다. 그리고 그 값을 num과 연산자1로 연산해준다

'이어져 온 값 + (숫자1 + 숫자2)'

즉 이런 상태로 다음 재귀로 넘기는 것

 

이렇게 끝까지 진행해주고 큐가 비게 되면 num을 ans와 비교하여 가장 큰 값을 구한다.

참고로 나올 수 있는 값은 int 범위의 음수 양수 전부 포함되므로 ans의 초기값은 0이 아니라 int 범위 바깥의 매우 작은 값으로 설정해준다.