[BOJ] #16637 _ 괄호 추가하기

[괄호 추가하기] https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

dfs를 이용하여 괄호를 추가할 수 있는 모든 경우의 수를 고려하여 계산하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <queue>
#include <algorithm>
#define MAX 2147483648

using namespace std;

int N, limit, max_val = -MAX;
int num[10], chk[10];
char op[9];

void solve(int idx);
int getResult();
int calcNum(int num1, int num2, char op);
int main() {
	scanf("%d", &N);

	limit = N / 2;
	for (int i = 0; i < limit; i++) {
		scanf("%d%c", &num[i], &op[i]);
	}
	scanf("%d", &num[limit]);

	solve(1);
	printf("%d\n", max_val);

	return 0;
}

void solve(int idx) {
	if (idx + 1 > limit) {
		max_val = max(max_val, getResult());
		return;
	}

	chk[idx] = 0;
	solve(idx + 1);
	chk[idx] = 1;
	if (chk[idx - 1]) return;
	solve(idx + 1);
}

int getResult() {
	int result = num[0];

	for (int i = 0; i < limit; i++) {
		if (chk[i + 1]) {
			result = calcNum(result, calcNum(num[i + 1], num[i + 2], op[i + 1]), op[i]);
			i++;
		}
		else result = calcNum(result, num[i + 1], op[i]);
	}

	return result;
}

int calcNum(int num1, int num2, char op) {
	switch (op) {
	case '+':
		return num1 + num2;
	case '-':
		return num1 - num2;
	case '*':
		return num1 * num2;
	}
}