백준 16637 : 괄호 추가하기 c++

코드

#include <iostream>
#include <algorithm>

using namespace std;

int N, maxans;
char math[20];

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

void dfs(int i, int a){
	if(i > N-1){
		maxans = max(maxans, a);
		return;
	}
	char op;
	if(i == 0) op = '+';
	else op = math[i-1];
	
	if(i + 2 <= N-1){
		int temp = cal(math[i]-'0', math[i+2] - '0', math[i+1]);
		dfs(i + 4, cal(a, temp, op));
	}
	
	dfs(i+2, cal(a, math[i] - '0', op));
	
}

int main(){
	
	cin >> N;
	
	maxans = -999999999;
	for(int i = 0; i < N; i++){
		cin >> math[i];
	}
	
	dfs(0, 0);
	cout << maxans;
	
	
	return 0;
}

알게된 점

삼성기출문제라길래 티어가 풀만한 것 같아서 풀어봤는데,,,

너무어렵다.

알고리즘을 생각하는건 쉬운데..

구현하는게 쉽지 않았다.

그냥 모든 경우의수를 다 해보면 되는데

그 모든 경우의수를 다 하기 위해서 DFS를 이용한다.

다른사람들의 풀이를 보긴 했는데,, 역시 삼성이다.

더 열심히 노력해야겠다.