[BOJ/백준][Gold5] 7490 : 0 만들기 (C++)

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

7490번: 0 만들기

 

 

[난이도] Gold5
[유형] 백트래킹

[풀이]
현재 값에 숫자를 한개만 사용해서 더하거나 빼주는 경우,
두개를 합쳐서 더하거나 빼주는 경우를 모두 해주는 백트래킹 함수를 작성하면 됩니다.
식을 출력해야 하기 때문에 전체 식을 함수의 인자로 전달하면서
정답인 경우에는 vector에 저장해줍니다.
오름차순으로 출력하려면  vector를 정렬해주기만 하면 됩니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int tc,N;
vector<string> ans;
void sol(int n,int v,string str){
    if(n==N+1) {
        if(v==0) ans.push_back(str.substr(1));
        return;
    }
    sol(n+1,v+n,str+"+"+to_string(n));
    if(n<=N-1) sol(n+2,v+10*n+n+1,str+"+"+to_string(n)+" "+to_string(n+1));

    if(n==1) return;

    sol(n+1,v-n,str+"-"+to_string(n));
    if(n<=N-1) sol(n+2,v-(10*n+n+1),str+"-"+to_string(n)+" "+to_string(n+1));
}
int main(){
    cin >> tc;
    while(tc--){
        cin >> N;
        sol(1,0,"");
        sort(ans.begin(),ans.end());
        for(auto a : ans) cout << a << '\n';
        cout << '\n';
        ans.clear();
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/7490.cpp