[C/C++] 백준 - 16637번 : 괄호 추가하기 (삼성 A형 기출문제)

https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

문제

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

입력

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

출력

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

 

풀긴 풀었는데 다른 분들 코드 보면 내 코드는 정말 길고, 난잡하다.

다른 분들이 백트래킹으로 푼 걸 보면 내 코드는 ㅠㅠ

 

나도 똑같이 백트래킹으로 풀었는데 나는

연산자의 위치를 vector에 pair형태로 위치(index)와 bool(True / False)로 넣어주었다.

예를 들면, 5 * 3 + 2가 있다면 벡터에

(1, False), (3, False)로 넣어준 것이다. bool은 조합을 사용했기 때문

그리고 연산자의 개수에 따라 해볼 수 있는 연산의 개수가 달라진다. 위 같은 경우에는 연산자를 2개 이상 묶을 수가 없다. 2개 이상 묶고자한다면 중첩괄호가 생기기 때문이다. 중첩괄호를 방지하기 위해서는 괄호를 2개 이상 묶고자한다면 처음 묶은 위치의 +2를 해주어야한다(벡터기준) 

ex) 3 + 1 - 4 * 2 ->

vector's idx : 0 -> (1, False),

vector's idx : 1 -> (3, False),

vector's idx : 2 -> (5, False)

인 경우 괄호를 1개만 사용할 경우 0, 1, 2 모두 가능하다

하지만 괄호를 2개 사용하고자 한다면, 0,2 경우만 가능하다. (0,1 or 1,2는 중첩괄호가 생기기 때문)

 

그래서 백트래킹할 때 괄호의 개수에 따라 다음 인덱스를 참조하는 기준을 달리하였다.

위 방식에 따라 묶을 수 있는 괄호의 개수에 따라 모든 경우의 수를 조합으로 따져보았고, 최대값을 최신화해주는 방식으로 구현했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#define INF 9876543210
using namespace std;

typedef long long ll;
typedef pair<int, int> pl;

// BOJ :: https://www.acmicpc.net/problem/16637

int N, Cnt, Cal_Cnt, Answer= -INF;
string s;
vector<pair<int, bool>> visited;
vector<int> v;
stack<int> stk;
stack<char> cal;

void dfs(int depth, int cnt, int start) {
	if (depth == cnt) {
		int nx = 0, jmp = 0; 
		for (int i = 0; i < s.size(); i++) {
			if (jmp > 0) {
				jmp--;
				continue;
			}
			if (i == v[nx] - 1) {
				int Sum = 0;
				switch (s[v[nx]]) {
				case '*' :
					Sum = (s[i] - '0') * (s[i + 2] - '0');
					break;
				case '+':
					Sum = (s[i] - '0') + (s[i + 2] - '0');
					break;
				case '-':
					Sum = (s[i] - '0') - (s[i + 2] - '0');
					break;
				}
				if (stk.empty()) 
					stk.push(Sum);
				else {
					int ADD = 0;
					switch (cal.top()) {
					case '*':
						ADD = stk.top() * (Sum);
						break;
					case '+':
						ADD = stk.top() + (Sum);
						break;
					case '-':
						ADD = stk.top() - (Sum);
						break;
					}
					stk.push(ADD);
				}
				// vector 범위 내 인덱스를 참조하기 위함
				if (nx + 1 < v.size()) nx++;
				jmp = 2;
			}
			else {
				if ('0' <= s[i] && s[i] <= '9') {
					if (stk.empty()) stk.push(s[i] - '0');
					else {
						int ADD = 0;
						switch (cal.top()) {
						case '*':
							ADD = stk.top() * (s[i] - '0');
							break;
						case '+':
							ADD = stk.top() + (s[i] - '0');
							break;
						case '-':
							ADD = stk.top() - (s[i] - '0');
							break;
						}
						stk.push(ADD);
					}
				}
				else cal.push(s[i]);
			}
		}
		Answer = max(Answer, stk.top());

		while (!stk.empty()) stk.pop();
		while (!cal.empty()) cal.pop();

		return;
	}

	if (depth == 1) {
		for (int i = start; i < visited.size(); i++) {
			if (!visited[i].second) {
				visited[i].second = true;
				v.push_back(visited[i].first);
				dfs(depth, cnt + 1, i + 1);
				visited[i].second = false;
				v.pop_back();
			}
		}
	}
	else {
		for (int i = start; i < visited.size(); i++) {
			if (!visited[i].second) {
				visited[i].second = true;
				v.push_back(visited[i].first);
				dfs(depth, cnt + 1, i + 2);
				visited[i].second = false;
				v.pop_back();
			}
		}
	}
}

int Init_Answer() {
	stack<int> Init_s;
	stack<char> Init_c;
	for (int i = 0; i < s.size(); i++) {
		if ('0' <= s[i] && s[i] <= '9') {
			if (Init_s.empty()) {
				Init_s.push(s[i] - '0');
			}
			else {
				int w = 0;
				switch (Init_c.top()) {
				case '*':
					w = Init_s.top() * (s[i] - '0');
					break;
				case '+':
					w = Init_s.top() + (s[i] - '0');
					break;
				case '-':
					w = Init_s.top() - (s[i] - '0');
					break;
				}
				Init_s.push(w);
			}
		}
		else {
			Init_c.push(s[i]);
		}
	}
	return Init_s.top();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	Cnt = N / 2;
	Cal_Cnt = Cnt / 2;

	cin >> s;
	int ps = 1;
	for (int i = 0; i < Cnt; i++) {
		visited.push_back({ ps, false });
		ps += 2;
	}

	Answer = max(Answer, Init_Answer());

	for (int i = 1; i <= Cal_Cnt; i++) dfs(i, 0, 0);

	cout << Answer << endl;

	return 0;
}