[백준/BOJ] 16637번 괄호 추가하기 (C++)

www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

삼성 A형 기출 문제 : 브루트 포스(완전 탐색)

 

입력된 수식이 3+8*7-9*2 라고 가정하고, 괄호를 형성할 수 있는 경우의 수를 따져봅시다.

 

괄호가 1개인 경우

(3+8)*7-9*2
3+(8*7)-9*2
3+8*(7-9)*2
3+8*7-(9*2)

 

괄호가 2개인 경우

(3+8)*(7-9)*2
(3+8)*7-(9*2)
3+(8*7)-(9*2)

 

괄호가 3개인 경우

(3+8)*(7-9)*2 => 괄호 3개를 만들 수 없다!

 

괄호를 형성할 수 있는 경우의 수를 직접 구해보면서 규칙을 찾아낼 수 있습니다. 조건에서 괄호안에는 연산자가 하나만 존재하고, 수식의 범위가 0~9이므로 무조건 3개 단위로 괄호가 형성됩니다. ex) (3 + 8) => 3, +, 8 이렇게 3개

위에서 3+8+7-9*2 수식은 따라서 괄호를 묶을 수 없으므로, 괄호를 묶지 않는 연산을 할 수 있게끔 조건을 걸어야합니다.

 

따라서 전체적인 풀이는 다음과 같습니다.

 

괄호 연산 함수 {
	+인 경우
    -인 경우
    *인 경우
}

DFS 함수 {
	1. 종료 조건
    2. 괄호를 묶는다. (이때 괄호를 묶을 수 있는지 조건 구축)
    3. 괄호를 묶지 않는다.
}

 

2번 괄호를 묶는 경우에, 앞서 언급했던 것처럼 괄호를 묶을 수 있는 조건인지 확인하고, 괄호 계산을 진행합니다.

괄호를 형성한 값은 예를들어 다음과 같습니다. 

 

괄호값  = a 연산자 b

여기서 a, 연산자, b를 (3 + 8) 라고 생각해봤을 때 다음과 같이 구할 수 있습니다.

 

a = 수식[idx]

b = 수식[idx + 2]

연산자 = 수식[idx + 1]

 

이런식으로 괄호 연산을 하고, 다시 DFS 탐색을 하는데, 이때 괄호 계산에 3개, 연산에 1개를 소모했기 때문에 현재 인덱스에 +4를 해서 다음 탐색을 진행합니다.

 

3번 괄호를 안묶는 경우에 현재 값과 다음 값을 연산합니다. 연산에 1개, 다음 값에 1개를 소모했기 때문에 다음 탐색을 진행할 때 인덱스를 +2해서 진행합니다.

 

※ answer를 임의의 음수 큰 값으로 초기화하지 않고 0으로 초기화하면 1-3 수식에서 -2가 아니라 0이 나올 수 있습니다. 이 점을 주의합시다. 

 

#include <iostream>
#include <vector>
using namespace std;

int n, answer = -2147000000;
string str;

int calculate(int a, int b, char op) {
	switch(op) {
		case '+':
			a += b; 
			break;
		case '-':
			a -= b;
			break;
		case '*':
			a *= b;
			break;
	}
	
	return a;
}

void DFS(int idx, int cur) {
	if(idx >= n) {
		answer = max(answer, cur);
		return;
	}
	
	char op = idx == 0 ? '+' : str[idx - 1];
	
	if(idx + 2 < n) {
		int bracket = calculate(str[idx] - '0', str[idx + 2] - '0', str[idx + 1]);
		DFS(idx + 4, calculate(cur, bracket, op));
	}
	
	DFS(idx + 2, calculate(cur, str[idx] - '0', op));
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> str;
	
	DFS(0, 0);
	cout << answer;
}

 

다른 풀이

#include<bits/stdc++.h>
#define f first
#define s second
#define lp(i, x, n) for(int i = x; i <= n; i++)

using namespace std;
typedef long long ll;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int t, n, m, k, sx, sy, ex, ey, x, y, z, answer = -2147000000, L, R;
string str;
vector<int> num;
vector<char> op;

void print(auto at) {
	for(auto it : at) {
		cout << it << " ";
	}
	cout << "\n";
}

int oper(char op, int num1, int num2) {
	if(op == '+') return num1 + num2;
	if(op == '-') return num1 - num2;
	if(op == '*') return num1 * num2;
}

void DFS(int idx, int sum) {
	if(idx == num.size() - 1) {
		answer = max(answer, sum);
		return;
	}
	
	DFS(idx + 1, oper(op[idx], sum, num[idx + 1]));
	
	if(idx + 2 <= num.size() - 1) {
		int tmp = oper(op[idx + 1], num[idx + 1], num[idx + 2]);
		DFS(idx + 2, oper(op[idx], sum, tmp));
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> str;
	for(char ch : str) {
		if(isdigit(ch)) num.push_back(ch - '0');
		else op.push_back(ch); 
	}
//	print(num);
//	print(op);
	
	DFS(0, num[0]);
	cout << answer;
}