백준 7490번 0 만들기 C++

출처 : https://www.acmicpc.net/problem/7490

 

우선 백트래킹을 이용하여 나열 가능한 모든 경우의 수를 탐색하였다.

 

탐색을 마칠 때, 숫자를 담는 벡터와 연산자를 담는 벡터 두 개를 새로 만들었다.

숫자를 담는 벡터에는 이어붙일 수 있는 숫자들을 넣고, ( 1+2 3 이면 1, 23 이 들어감)

연산자를 넣는 벡터에는 +와 - 연산자만 넣었다.

그러면 예를들어 1+2 3-4 5 인 경우에는 숫자를 담는 벡터에는 1, 23, 45가 들어가고 연산자를 담는 벡터에는 +, - 이 들어간다.

 

새로 만든 두 벡터를 이용해 값을 계산해서 0이 되는 경우만 출력하도록 하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int t, n;
vector<char> v;

void Solve(int num) {
	if (num >= n) {
		int tmp = 0;
		char last_operator = ' ';
		vector<int> nums;
		vector<char> operators;
		for (int i = 0; i < n; i++) {
			if (last_operator != ' ') {
				nums.push_back(tmp);
				tmp = i + 1;
			}
			else {
				tmp = tmp * 10 + i + 1;
			}
			if (v.size() > i) {
				last_operator = v[i];
				if (v[i] != ' ') {
					operators.push_back(v[i]);
				}
			}
		}
		nums.push_back(tmp);
		int sum = nums[0];
		for (int i = 0; i < operators.size(); i++) {
			if (operators[i] == '+') {
				sum = sum + nums[i + 1];
			}
			else {
				sum = sum - nums[i + 1];
			}
		}
		if (sum == 0) {
			for (int i = 0; i < n; i++) {
				cout << i + 1;
				if (v.size() > i) {
					cout << v[i];
				}
			}
			cout << "\n";
		}
		return;
	}

	v.push_back(' ');
	Solve(num + 1);
	v.pop_back();

	v.push_back('+');
	Solve(num + 1);
	v.pop_back();

	v.push_back('-');
	Solve(num + 1);
	v.pop_back();
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> t;
	while (t--) {
		cin >> n;
		Solve(1);
		cout << "\n";
	}
};