백준 16637_괄호 추가하기(C++)

[문제 풀이]

브루트 포스(Brute force)를 이용하여 문제를 풀었습니다.

 

이 문제는 주어진 수식에 괄호를 쳐서 나올 수 있는 가장 큰 수를 찾는 것입니다. 여기서 괄호를 치는 조건이 존재합니다. 괄호는 하나의 연산자만 포함할 수 있습니다. 즉 ( A + B )와 같이 숫자 두 개 연산자 하나의 경우만 묶을 수 있습니다. 또한 괄호 안에 괄호가 포함돼서는 안됩니다. 이것을 잘 지키면 문제가 쉽게 풀립니다. 단 하나의 조건이 있다면 문제의 답은 음수가 나올 수도 있다는 것을 염두해야 합니다.

 

코드 설명

• 들어온 문자열이 1자리이면 그 수를 출력합니다.
• 아닌 경우 문자열의 0 번째 숫자만 선택하는 경우와 0 ~ 2 까지 괄호로 묶는 경우로 나눠서 함수를 실행합니다.
• 만약 DFS함수에 들어온 매개변수가 문자열의 크기를 넘어가게 된다면 값을 비교해 줍니다.
•  DFS함수에 들어온 매개변수가 문자열을 넘지 않는 경우 문자열 이전 인덱스의 연산자를 비교하여 실행해 줍니다.
• 매개변수로 주어진 인덱스 뒤에 문자가 더 존재한다면 괄호로 묶는 것 또한 실행해 줍니다.

[코드]

#include<iostream>
#include<string>
#include<stack>

using namespace std;

int answer = -987654321;
string str;

int calculater(int idx, int jdx) {

	int temp1 = str[idx] - '0';
	int temp2 = str[jdx] - '0';

	if (str[idx + 1] == '+')
		return temp1 + temp2;
	else if (str[idx + 1] == '-')
		return temp1 - temp2;
	else if (str[idx + 1] == '*')
		return temp1 * temp2;

}

void DFS(int idx, int temp_result) {

	if (idx >= str.size()) {
		if (temp_result > answer)
			answer = temp_result;
		return;
	}
	
	if (str[idx - 1] == '+') {
		DFS(idx + 2, temp_result + (str[idx] - '0'));

		if (idx + 2 < str.size())
			DFS(idx + 4, temp_result + calculater(idx, idx + 2));

	}
	
	else if (str[idx - 1] == '-') {
		DFS(idx + 2, temp_result - (str[idx] - '0'));

		if (idx + 2 < str.size())
			DFS(idx + 4, temp_result - calculater(idx, idx + 2));
	}
	
	else if (str[idx - 1] == '*') {
		DFS(idx + 2, temp_result * (str[idx] - '0'));

		if (idx + 2 < str.size())
			DFS(idx + 4, temp_result * calculater(idx, idx + 2));
	}
	
	
}

int main() {

	int N; cin >> N;
	
	cin >> str;
		

	if (N > 2) {
		DFS(2, str[0] - '0');
		DFS(4, calculater(0, 2));
	}
	else
		answer = str[0] - '0';
	
	cout << answer << endl;

	return 0;

}