[c++] 백준 16637, 괄호 추가하기

백준 16637

🌲 문제 요약

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 결과의 최댓값을 구하는 문제.

🌲 문제 풀이

입력받은 수식의 정수와 연산자를 각각 벡터 num과 oper에 담는다. 현재 위치를 가리키는 here, 현재까지의 계산 값을 가리키는 _num을 인자로 갖는 함수 go를 재귀적으로 호출하여 문제를 해결한다.
세 개의 정수 중에서 앞의 두 개 정수와 뒤의 두 개 정수를 먼저 계산하는 경우를 각자 나누어 계산한다.

🌲 주의

here과 num.size() - 1의 값이 같아지면 ret과 _num을 비교하여 더 큰 값을 ret에 저장한 뒤, return한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int n, ret = -987654321;
string s;
vector<int> num;
vector<char> oper;

int calc(char a, int b, int c) {
	if (a == '+') return b + c;
	if (a == '-') return b - c;
	if (a == '*') return b * c;
}

void go(int here, int _num) {
	if (here == num.size() - 1) {
		ret = max(ret, _num);
		return;
	}
	go(here + 1, calc(oper[here], _num, num[here + 1]));
	if (here + 2 < num.size()) {
		int tmp = calc(oper[here + 1], num[here + 1], num[here + 2]);
		go(here + 2, calc(oper[here], _num, tmp));
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	cin >> s;
	for (int i = 0; i < n; i++) {
		if (!(i % 2)) num.push_back(s[i] - '0');
		else oper.push_back(s[i]);
	}
	go(0, num[0]);
	cout << ret << '\n';
	
	return 0;
}