[백준][C++] 16637. 괄호 추가하기

삼성 A형 문제 중 하나인데 삼성은 브루트 포스를 좋아하나보다...

 

수식이 주어지면 수식에 적절하게 괄호를 넣어 최대 결과값을 구하는 문제이다.

중첩 괄호는 허용되지 않고,  괄호 안에는 연산자가 1개만 들어있어야 한다.

 

수식을 string으로 입력받은 후 숫자는 숫자끼리, 연산자는 연산자끼리 따로 배열에 저장했다.

그 다음 dfs를 사용해 "현재 연산자"를 기준으로

괄호를 추가하는 경우와 그렇지 않은 경우로 나누어서 연산을 수행했다.

 

예를 들어, 3 + 8 * 7 - 9 에서 현재 연산자가 +인 경우,

 

1. 현재 연산자를 기준으로 괄호 추가

(3 + 8)을 계산한 후 다음 연산자인 * 대해 dfs(*, 11) 수행

 

2. 다음 연산자를 기준으로 괄호 추가

(8 * 7)을 계산한 후 현재 피연산자(3)를 계산한다. (8 * 7) + 3

그리고 다다음 피연산자인 -에 대해 dfs(-, 59) 수행

 

// 16637_괄호_추가하기.cpp
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAX 20

int n; // 수식 길이
int max_result = -987654321; // 최대값

char oper[MAX];
int num[MAX];

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

void dfs(int idx, int result) { // idx: 연산자 인덱스, result: 현재까지의 연산 결과
	/* 연산자 개수 = n / 2 */
	if (idx >= n / 2) { // 끝까지 탐색하면 종료
		max_result = max(max_result, result);
		return;
	}

	// 현재 연산자 기준 괄호 추가
	char op = oper[idx];
	int cur_result = cal(result, num[idx + 1], op); // 다음으로 오는 수와 연산
	dfs(idx + 1, cur_result);

	// 다음 연산자 기준 괄호 추가
	if (idx + 1 < n / 2) {
		int next_result = cal(num[idx + 1], num[idx + 2], oper[idx + 1]); // 다음 연산자에 괄호 추가해 연산
		int cur_result = cal(result, next_result, op);
		dfs(idx + 2, cur_result);
	}
}

int main()
{
	scanf("%d", &n);

	string exp;
	cin >> exp;

	int o_idx = 0;
	int n_idx = 0;
	/* 연산자 배열, 피연산자 배열 따로 저장 */
	for (int i = 0; i < n; i++) {
		if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*') {
			oper[o_idx++] = exp[i];
		}
		else num[n_idx++] = exp[i] - '0';
	}

	dfs(0, num[0]);

	printf("%d", max_result);

	return 0;
}