[DFS 단순] 백준 16637 괄호 추가하기 C++

※ 문제

https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

※ 풀이

1) DFS 필요

#include<bits/stdc++.h>

using namespace std;

int n, ans = INT_MIN; // 음수 최저값 필요
string str;

int cal(int depth, int a, int b) {
	if (depth < 0) { // 인덱스 0 조심
		return (a + b);
	}
	if (str[depth] == '+') return (a + b);
	else if (str[depth] == '-') return (a - b);
	else if (str[depth] == '*') return (a * b);
}

void dfs(int depth, int val) { // depth 피연산자 확인
	if (depth == n - 1) { // 마지막 피연산자 계산
		ans = max(ans, cal(depth - 1, val, (str[depth] - '0')));
		return;
	}
	if (depth >= n) {
		ans = max(ans, val);
		return;
	}

	int temp = cal(depth + 1, (str[depth] - '0'), (str[depth + 2] - '0'));
	int res1 = cal(depth - 1, val, temp);
	int res2 = cal(depth - 1, val, (str[depth] - '0'));

	dfs(depth + 4, res1); // str[depth]와 str[depth+2] 괄호 계산
	dfs(depth + 2, res2); // str[depth]가 괄호 안에 없을 때 계산
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> str;

	dfs(0, 0);

	cout << ans;
}