[백준] 7490 0 만들기 (C++)

👓 문제 설명

---

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

---

💣 제한 사항

• 첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).
• 각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9)
• 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

---

🚨 접근 방법

수식을 완성하게 만드는 연산자의 조합을 구한 후
그 수식이 0이 되었을 때 수식을 출력하는 문제이다.

단순히 사칙연산의 연산자가 아닌
' '의 연산자가 주어진다.

이는 앞의 숫자와 뒤의 숫자를 연결하는 연산자이다.

따라서 공백의 연산자를 만났을 때

string의 맨 뒤에 새로운 숫자를 추가해주었다.

ex) 1-2 3 -> 1-23

이후 연산자를 통해 수식을 계산한 뒤 0인지 판단해주었다.

그러나 정답을 출력할 때는 1-23이 아닌 1-2 3을 출력해주어야 하므로 기존에 붙여놓은 숫자를 다시 공백을 추가해 되돌려주어야 한다.

---

🚈 풀이

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

int t, n;
char nums[11] = {'0', '1','2','3','4','5','6','7','8','9' };
char oper[3] = { ' ','+','-' };

bool print(string s) {
	vector<int>v;
	int cur = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '+') {
			v.push_back(cur);
			cur = 0;
			v.push_back(-1);
		}
		else if (s[i] == '-') {
			v.push_back(cur);
			cur = 0;
			v.push_back(-2);
		}
		else {
			cur *= 10;
			cur += s[i] - '0';
			if (i == s.length() - 1)v.push_back(cur);
		}
	}

	// 초기 숫자 구하기
	int f_num = 0;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] > 0) {
			f_num *= 10;
			f_num += v[i] - 0;
		}
		else break;
	}

	int ans = f_num;
	for (int i = 1; i < v.size(); i++) {
		if (v[i] == -1) {
			ans +=  v[i + 1];
		}
		else if (v[i] == -2) {
			ans -= v[i + 1];
		}
	}

	if (ans == 0)return true;
	return false;
}

void func(int depth, int cur, string s) {
	if (depth == n-1) {
		if (print(s)) {
			string result = "";
			for (int i = 0; i < s.length(); i++) {
				if (s[i] > '0' && s[i + 1] > '0') {
					result += s[i];
					result += ' ';
				}
				else {
					result += s[i];
				}
			}
			cout << result << "\n";
		}
	}
	for (int i = cur; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			string temp = s;
			if (oper[j] == ' ') {
				temp += nums[i];
			}
			else {
				temp += oper[j];
				temp += nums[i];
			}
			func(depth + 1, i + 1, temp);
		}
	}
}


int main() {
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		func(0, 2, "1");
		cout << "\n";
	}
	return 0;
}