[G1] 백준 16638번 괄호 추가하기 2 C++ 구현, 백트래킹

리뷰

 

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

백트래킹으로 괄호를 배치하는 모든 경우를 찾고, 사칙 연산을 구현하여 최대값을 구하는 문제

 

 

전역 변수

• n : 수식의 길이를 저장할 변수
• s : 수식을 저장할 문자열
• op : 연산자를 저장할 배열
• num : 숫자를 저장할 배열
• c_op : 선택한 연산자를 저장할 벡터
• c_num : 선택한 숫자를 저장할 벡터
• ans : 정답을 저장할 변수

 

함수

1. bt

void bt(int level, bool prev) {
	if (level >= n / 2) {
		vector<int> temp(1, c_num[0]);
		//cout << c_op.size() << " " << c_num.size() << "\n";
		//cout << c_num[0];
		//for (int i = 0; i < c_op.size(); ++i) cout << c_op[i] << c_num[i + 1];
		//cout << "\n";
		for (int i = 0; i < c_op.size(); ++i) {
			//cout << temp.back() << "\n";
			if (c_op[i] == '+') temp.push_back(c_num[i + 1]);
			else if (c_op[i] == '-') temp.push_back(-c_num[i + 1]);
			else temp.back() *= c_num[i + 1];
		}

		//cout << temp.back() << "\n";
		int sum = 0;
		for (int i : temp) sum += i;
		//cout << sum << "\n";
		ans = max(ans, sum);
		return;
	}

	int a = num[level + 1];
	char b = op[level];

	if (!prev) {
		int c = c_num.back(); c_num.pop_back();

		if (b == '+') c_num.push_back(c + a);
		else if (b == '-') c_num.push_back(c - a);
		else c_num.push_back(c * a);
		bt(level + 1, true);
		c_num.pop_back();
		if (b == '+') c_num.push_back(c);
		else if (b == '-') c_num.push_back(c);
		else c_num.push_back(c);
	}

	c_num.push_back(a);
	c_op.push_back(b);
	bt(level + 1, false);
	c_num.pop_back();
	c_op.pop_back();
}

 

괄호를 배치하거나 배치하지 않는 경우를 분기처리하고, 기저 조건에서 연산을 수행 후 ans를 최신화 하는 함수

 

 

문제풀이

1. n, s값을 입력 받고, s를 순회하며 연산자는 op배열에, 숫자는 num배열에 저장한다.
2. c_num에 초기 숫자인 num[0]을 추가한다.
3. bt함수에 0, false를 매개변수로 전달하여 함수를 호출한다.
4. bt함수는 변수 level, prev에 매개변수를 전달받아 파싱한다.
5. 기저 조건으로 level이 n/2에 도달했다면, 정수형 벡터 temp를 c_num[0]을 넣은 상태로 초기화하고, c_op를 순회한다.
6. 연산자가 '+'라면 temp에 다음 숫자를 추가한다.
7. 연산자가 '-'라면 temp에 다음 숫자를 음수로 추가한다.
8. 연산자가 '*'라면 temp의 맨 뒷 요소에 다음 숫자를 곱한다.
9. 변수 sum을 0으로 초기화 하고, temp를 순회하며 각 요소를 sum에 더해준다.
10. ans를 sum과 비교하여 더 큰 값으로 최신화 하고, 리턴 처리한다.
11. 기저 조건에 해당하지 않는다면 변수 a에 다음 숫자를, b에 다음 연산자를 저장한다.
12. prev가 false라면 괄호를 씌우는 로직을 실행 후 재귀를 수행하고, 재귀를 빠져나오며 원상 복구를 해준다.
13. 괄호를 씌우지 않는 로직도 실행 후 재귀를 수행하고, 재귀를 빠져나오며 원상 복구를 해준다.
14. bt함수가 종료된 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

1. 구현을 완료하고 예제 테스트 시 4번에서 에러가 발생하였다.
2. 괄호를 씌우는 과정에서 c_num의 back()에 바로 연산처리한 것이 원인이었다.
3. 0을 곱하는건 문제가 없지만 원상 복구를 해줄때 0으로 나누는 경우가 있어서 DivideZero에러가 발생한 듯 하다.
4. 별도의 변수 c에 c_num의 back()을 저장하고 pop처리 후 안전하게 처리해주어 AC를 받았다.

 

참고 사항

1. 중첩된 괄호는 사용할 수 없다는 조건으로 인해 prev를 사용해 연속으로 괄호를 사용할 수 없게 구현하였다.
2. 음수가 정답으로 나올 수 있으므로 ans의 초기값은 매우 작은 음수로 설정해주었다.

 

정답 코드

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

int n;
string s;
char op[10];
int num[11];
vector<char> c_op;
vector<int> c_num;
int ans = -2e9;

void bt(int level, bool prev) {
	if (level >= n / 2) {
		vector<int> temp(1, c_num[0]);
		//cout << c_op.size() << " " << c_num.size() << "\n";
		//cout << c_num[0];
		//for (int i = 0; i < c_op.size(); ++i) cout << c_op[i] << c_num[i + 1];
		//cout << "\n";
		for (int i = 0; i < c_op.size(); ++i) {
			//cout << temp.back() << "\n";
			if (c_op[i] == '+') temp.push_back(c_num[i + 1]);
			else if (c_op[i] == '-') temp.push_back(-c_num[i + 1]);
			else temp.back() *= c_num[i + 1];
		}

		//cout << temp.back() << "\n";
		int sum = 0;
		for (int i : temp) sum += i;
		//cout << sum << "\n";
		ans = max(ans, sum);
		return;
	}

	int a = num[level + 1];
	char b = op[level];

	if (!prev) {
		int c = c_num.back(); c_num.pop_back();

		if (b == '+') c_num.push_back(c + a);
		else if (b == '-') c_num.push_back(c - a);
		else c_num.push_back(c * a);
		bt(level + 1, true);
		c_num.pop_back();
		if (b == '+') c_num.push_back(c);
		else if (b == '-') c_num.push_back(c);
		else c_num.push_back(c);
	}

	c_num.push_back(a);
	c_op.push_back(b);
	bt(level + 1, false);
	c_num.pop_back();
	c_op.pop_back();
}

int main() {
	cin >> n >> s;
	for (int i = 0; i < n; ++i) {
		if (i % 2) op[i / 2] = s[i];
		else num[i / 2] = s[i] - '0';
	}

	c_num.push_back(num[0]);
	bt(0, false);
	cout << ans;
}