7490 - 0 만들기

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

7490번: 0 만들기

생각해 보기

1. 연산자 순서는  | + | -  이다.

2. 다음 숫자를 계산하기 이전에 이전 연산의 결과를 처리해 버리면 안 된다.

3. 1-2 3 에서 1-2를 먼저 계산 해버리면 3을 사용하기 위해 이전 값을 더해주거나 빼주어야 하는 과정이 추가된다.

4. 마지막에는 남은 연산을 진행해주고 값을 확인하면 된다.

코드

#include<iostream>
#include<string>

using namespace std;

int T;
int N;
int cnt = 0;

void input(){
    cin>>T;
}

int calc(int num1, int num2, char op){
    switch (op)
    {
    case '+':
        return num1 + num2;
        break;
    
    case '-':
        return num1 - num2;
        break;
    default:
        return -1;
        break;
    }
}

void dfs(int num, char op, int ret, string str, int space){
    if(num == N){
        if(calc(ret, space, op) == 0){
                cout<<str<<'\n';
            }
        
        return;
    }

    int nnum=num+1;
    int nret=calc(ret,space,op);
    dfs(nnum, op ,ret,str+' '+to_string(nnum), space*10+nnum);
    dfs(nnum, '+',nret ,str+'+'+to_string(nnum), nnum);
    dfs(nnum, '-',nret ,str+'-'+to_string(nnum), nnum);
}

void solution(){
    while(T--){
        cin>>N;
        cnt = 0;

        dfs(1,'+', 0, "1",1);
        cout<<'\n';
    }
}

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

    input();
    solution();

    return 0;
}