[G3] 백준 16637번 괄호 추가하기 C++ 구현, 백트래킹

리뷰

 

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

주어지는 연산자가 포함된 문자열로 이루어진 수열에서 괄호를 적절히 쳐서 최대값을 만드는 문제

처음엔 모든 경우에 대해 괄호를 씌워주었는데, 괄호가 중첩되면 안된다는 조건이 있었다.

추가로, 음수 정답이 나오는 예제가 없으니 해당 부분을 놓치기 쉬운 것 같다.

 

 

전역 변수

• n : 입력되는 수열 형태의 문자열의 길이
• max_lv : 재귀를 멈출 기저조건에 해당하는 레벨
• ans : 정답을 출력하기 위한 변수, 초기값은 매우 작은 음수값으로 초기화 해준다.
• s : 수열 형태의 문자열을 입력받을 변수
• nums : 수열에서 숫자만 따로 저장하기 위한 정수형 벡터
• ops : 수열에서 연산자만 따로 저장하기 위한 문자형 벡터

 

함수

1. init

void init()

 

입력 받은 문자열에서 정수와 연산자를 분리하기 위한 함수

1. 문자열 s의 길이 n만큼 반복문을 개행한다.
2. 만약 탐색하는 인덱스가 홀수라면 ops에 연산자를 전달한다.
3. 반대로 짝수일 경우에는 nums에 정수를 전달한다.

 

2. chk

int chk(const vector<int>& path)

 

현재 괄호를 친 상태를 기준으로 연산을 진행하는 함수

1. 매개 변수로 path를 받는데 해당 벡터엔 괄호를 적용할 연산자의 인덱스가 담겨있다.
2. nums와 ops 벡터를 각각 tn, to의 벡터에 깊은 복사를 진행해 준다.
3. path를 순회하며 괄호를 적용할 연산자를 참조하여 해당 인덱스의 앞뒤 숫자의 연산을 미리 해준다.
4. 연산을 마친 후엔 +, -, *가 아닌 다른 값으로 지정해 준다, 나는 공백으로 지정해 주었다.
5. 정수형 변수 sum에 tn의 0번째 인덱스를 저장해 준다.
6. 다시 to배열을 돌며 현재 연산자가 이미 괄호로 처리된(나의 경우엔 공백) 경우 continue 처리해 준다.
7. 그게 아니라면 +, -, *에 맞게 tn배열의 값을 sum과 연산을 진행해 주면 된다.

 

3. bt

void bt(int level, vector<int> path)

 

백트래킹을 통해 괄호를 놓을 수 있는 모든 경우를 탐색하는 함수

1. 우선 백트래킹 시 고려할 방법은 괄호를 적용하거나 적용하지 않는 두가지 경우를 체크하는 것이다.
2. 기저조건은 level이 max_lv에 도달했을 경우이다.
3. 기저조건에 도달했다면 ans를 chk함수를 통해 리턴 받아온 값과 비교하여 큰 값으로 교체해 준 뒤 리턴한다.
4. 기저조건에 도달하지 않았다면 일단 괄호를 추가하지 않고 그대로 재귀 레벨을 올려 진행해 준다.
5. 이후 만약 path가 비었다면 path에 level을 추가하고 재귀를 진행해 준다.
6. 만약 path가 빈 상태가 아니라면 path의 back의 값을 체크를 진행해 주어야 한다.
7. 이유는 괄호를 중첩된 상태로 넣을수 없기 때문이다, level - 1보다 path.back()이 작으면 재귀를 진행한다.
8. 이때 path는 깊은 복사를 진행했는데 생각해보니 딱히 깊은 복사 안해도 될듯?

 

문제풀이

1. n, s값을 입력 받고 init 함수를 호출하여 nums, ops 벡터를 초기화 해준다.
2. max_lv를 n / 2로 초기화 해주고, 빈 정수형 벡터 path를 초기화 해준다.
3. bt함수에 0, path를 매개변수로 전달하여 백트래킹을 진행해 준다.
4. ans에 저장된 값을 출력해 준다.

 

참고 사항

음수 정답이 나올 경우를 잘 대비하자, 나처럼 ans의 초기값을 0으로 할당하면 안된다.

 

 

정답 코드

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

int n, max_lv, ans = -2e9;
string s;
vector<int> nums;
vector<char> ops;

void init() {
	for (int i = 0; i < n; i++) {
		if (i % 2) ops.push_back(s[i]);
		else nums.push_back(s[i] - '0');
	}
}

int chk(const vector<int>& path) {
	vector<int> tn = nums;
	vector<char> to = ops;
	for (int i : path) {
		char op = to[i];
		if (op == '+') tn[i] += tn[i + 1];
		else if (op == '-') tn[i] -= tn[i + 1];
		else tn[i] *= tn[i + 1];
		to[i] = ' ';
	}
	
	int sum = tn[0];
	for (int i = 0; i < max_lv; i++) {
		char op = to[i];
		if (op == ' ') continue;
		else if (op == '+') sum += tn[i + 1];
		else if (op == '-') sum -= tn[i + 1];
		else sum *= tn[i + 1];
	}
	return sum;
}

void bt(int level, vector<int> path) {
	if (level == max_lv) {
		ans = max(ans, chk(path));
		return;
	}

	bt(level + 1, path);
	if (path.empty()) {
		path.push_back(level);
		bt(level + 1, path);
	}
	else if (path.back() < level - 1) {
		vector<int>new_path = path;
		new_path.push_back(level);
		bt(level + 1, new_path);
	}
}

int main() {
	cin >> n >> s;

	init();
	max_lv = n / 2;
	vector<int> path;
	bt(0, path);
	cout << ans;
}