BOJ-16637 괄호 추가하기

필요한 지식

1. 완전탐색

접근

연산을 앞에서 부터 해주므로 앞에서 부터 연산자와 숫자를 한 단위로 보면서 재귀로 완전탐색한다.

연산자와 숫자를 한단위로 볼때 가능한 연산의 경우는 두가지 이다.

1. 현재 숫자를 괄호치지 않고 이때까지 계산한 값과 연산하는 경우

2. 현재 숫자와 다음숫자를 괄호를 치고 이때까지 계산한 값과 연산하는 경우

인덱스와 조심하고, 답이 음수도 나올수 있으므로 최대값을 저장하는 변수를 0으로 초기화 하면 안되는 것도 조심하면 쉽게 해결 할 수 있다.

코드(C++)

#include <iostream>
#include <string>
#include <algorithm>
#include <limits.h>
using namespace std;
int ans = INT_MIN, n;
string s;
int cal(int a, int b, char op) {
	if (op == '+') return a + b;
	if (op == '-') return a - b;
	if (op == '*') return a * b;
}
void go(int idx, int res) {
	if (idx >= n) {
		ans = max(ans, res);
		return;
	}
	if (!idx)go(idx + 2, cal(res, s[idx] - '0', '+'));
	else go(idx + 2, cal(res, s[idx] - '0', s[idx - 1]));
	if (idx + 2 < n) {
		if (idx)go(idx + 4, cal(res, cal(s[idx] - '0', s[idx + 2] - '0', s[idx + 1]), s[idx - 1]));
		else go(idx + 4, cal(res, cal(s[idx] - '0', s[idx + 2] - '0', s[idx + 1]), '+'));
	}
	return;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	go(0, 0);
	cout << ans;
	return 0;
}