백준 7490 0 만들기 C++

간단한 해설

n이 최대 9까지이고, 경우의 수가 공백, +, -의 3가지이므로, 연산자를 고르는 경우의 수는 3^8개이다.

브루트포스를 해서 전부 세보자.

 

그런데 C++로 하면 파싱에 어려움을 겪을 수 있다.

 

C++에서 파싱은 기본적으로 노가다이다.(설명을 위해 공백도 연산자라 하자.)

나의 경우, 연산자를 고르고 연산자가 공백인 경우, 공백이 존재하는 문자열과 없는 문자열 2개를 만든다.

정답을 출력할 경우 공백이 존재하는 문자열을 사용하여 출력하고, 그게 아니면 공백이 존재하지 않는 문자열로 파싱을 한다.

 

공백이 존재하지 않는 문자열을 이용하여 파싱할 때, 일단 연산자의 위치를 배열에 저장한다.

그리고 연산자의 위치를 토대로 stoi()를 적절히 이용하면 된다.

 

 

답

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<char> picker;
vector<char> calc;
int n;
void pick(int toPick){
	if(toPick==0){
		string str="";
		string ansStr="";
		for(int i=0;i<picker.size();++i){
			str+=to_string(i+1);
			ansStr+=to_string(i+1);
			ansStr+=picker[i];
			if(picker[i]!=' '){
				str+=picker[i];
			}
		}
		str+=to_string(picker.size()+1);
		ansStr+=to_string(picker.size()+1);
		vector<int> findOperator;
		for(int i=0;i<str.size();++i){
			if(str[i]=='+'||str[i]=='-') findOperator.push_back(i);
		}
		if(!findOperator.empty()){
			vector<int> v;
			string tmp="";
			for(int i=0;i<findOperator[0];++i){
				tmp+=str[i];
			}
			v.push_back(stoi(tmp));
			for(int i=1;i<findOperator.size();++i){
				string tmptmp="";
				for(int j=findOperator[i-1]+1;j<findOperator[i];++j){
					tmptmp+=str[j];
				}
				int flag=1;
				if(str[findOperator[i-1]]=='-'){
					flag=-1;
				}
				v.push_back(flag*stoi(tmptmp));
			}
			tmp="";
			for(int i=findOperator[findOperator.size()-1]+1;i<str.size();++i){
				tmp+=str[i];
			}
			int flag=1;
			if(str[findOperator[findOperator.size()-1]]=='-') flag=-1;
			v.push_back(flag*stoi(tmp));
			int ans=0;
			for(int i=0;i<v.size();++i){
				ans+=v[i];
			}
			if(ans==0){
				cout<<ansStr<<"\n";
			}
		}
		return;
	}
	picker.push_back(' ');
	pick(toPick-1);
	picker.pop_back();
	picker.push_back('+');
	pick(toPick-1);
	picker.pop_back();
	picker.push_back('-');
	pick(toPick-1);
	picker.pop_back();
}
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t-->0){
		cin>>n;
		pick(n-1);
		cout<<"\n";
	}
}