[백준OJ] 7490번 0 만들기

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

7490번: 0 만들기

---

 

-풀이-

N의 최댓값이 9이기 때문에, DFS를 이용하여 모든 경우를 탐색해보아도, O(3⁹)이 걸리기 떄문에 DFS를 이용했다.

공백, 더하기, 빼기를 넣은 모든 경우에서, 계산을 했을 때 0이되면 출력을 하면된다. 이때 결과가 아스키순서를 따라야 하므로, 공백->더하기->빼기 순으로 실행시켜주어야 한다.

 

-시간복잡도-

모든 경우가 3^9 이므로, O(3⁹) = O(1)이 된다.

 

-코드-

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

void dfs(int now,string st_now,int n){
    if(now==n){
        int sum=0;
        char sign='+';
        int temp=0;
        for(int i=0;i<st_now.size();i++){
            if(st_now[i]>='0'&&st_now[i]<='9'){
                temp=temp*10+(st_now[i]-'0');
                if(i==st_now.size()-1){
                    if(sign=='+'){
                        sum+=temp;
                    }
                    else{
                        sum-=temp;
                    }
                }
            }
            else if(st_now[i]=='+'||st_now[i]=='-'){
                if(sign=='+'){
                    sum+=temp;
                }
                else{
                    sum-=temp;
                }
                temp=0;
                sign=st_now[i];
                
            }
        }
        if(sum==0){
            cout<<st_now<<"\n";
        }
        return;
    }
    
    dfs(now+1,st_now+" "+to_string(now+1),n);
    dfs(now+1,st_now+"+"+to_string(now+1),n);
    dfs(now+1,st_now+"-"+to_string(now+1),n);
    
}

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        
        dfs(1,"1",n);
        cout<<"\n";
    }
}