BOJ 16637: 괄호 추가하기

#BOJ 16637: 괄호 추가하기

16637번: 괄호 추가하기

#풀이

 

괄호를 추가해서 최대값을 찾는 문제이다.

 

맨 처음엔 조건문으로 해결하려다가 n의 크기가 그렇게 크지 않아 dfs를 재귀함수로 만들어 사용하였다.

 

괄호를 안칠 때

괄호를 칠 때

인덱스가 0일 때

 

위에 조건문을 사용하여 재귀함수를 사용하여 풀었다.

 

또한 가장 큰 값이 음수가 나올 수 있으므로 ans는 가장 작은 수로 해야한다.

 

#코드

#include<bits/stdc++.h>

using namespace std;
int n;
int ans = -0x3f3f3f3f;
string str;
int oper(int a, int b, char op){
	int sum = 0;
	if(op == '+')
		sum += a + b;
	else if(op == '-') sum += a-b;
	else sum+= a* b;
	
	return sum;

}

void back_func(int idx, int cur){
	if(idx >= n)
	{
		ans = ans < cur ? cur : ans;
		return;
	}
	if(idx== 0)
	{
		back_func(idx+1, oper(str[idx]-'0', 0, '+')); //괄호 x
		back_func(idx+3, oper(str[idx]-'0', str[idx+2]-'0', str[idx+1]));//괄호 o
	}
	if(idx != 0){
		if(idx + 3 < n){
			back_func(idx+4, oper(cur, oper(str[idx+1] -'0', str[idx+3] -'0', str[idx+2]), str[idx]));
		}
		back_func(idx+2, oper(cur, str[idx+1]-'0', str[idx])); 
	}

}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	
	cin >> str;
	
	back_func(0, 0);
	
	cout << ans << '\n';
	
	
	return 0;
}