[백준 - 7490] 0 만들기 [C++]

1. 문제

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

7490번: 0 만들기

 

2. 풀이

전형적인 브루트포스 문제이다..

나의 경우 두번 '출력 형식이 잘못되었습니다' 를 받았었는데..

'각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.' 이것을 간과한채 제출했었다..

케이스별로 한 줄씩 띄워주니까 맞았다..

 

문제는 연산자 3개로 표현가능한 모든 식을 만들어보고 그 식을 계산했을 때 0인지 판정하면된다.

c++에는 eval함수가 없어서 직접 구현했다..

 

3. 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
int T, n;
char opers[3] = { ' ', '+', '-' };
vector<string> answers;

string makeExpression(vector<int> numbers, vector<char>& operators) {
    string ret = to_string(numbers[0]);
    for(int i=1; i<n; i++) {
        ret += operators[i-1];
        ret += to_string(numbers[i]);
    }

    return ret;
}

int eval(string expression) {
    int ret = 0;
    string num = "";
    char oper = '+';
    for(int i=0; i<expression.size(); i++) {
        if(expression[i] == ' ') continue;
        if(expression[i] == '+') {
            if(oper == '+') ret += atoi(num.c_str());
            else ret -= atoi(num.c_str());
            oper = '+';
            num = "";
        }
        if(expression[i] == '-') {
            if(oper == '+') ret += atoi(num.c_str());
            else ret -= atoi(num.c_str());
            oper = '-';
            num = "";
        }
        else {
            num += expression[i];
        }
    }

    if(oper == '+') ret += atoi(num.c_str());
    else ret -= atoi(num.c_str());
    
    return ret;
}

void dfs(vector<int> numbers, vector<char>& operators) {
    // 종료조건
    if(operators.size() == n-1) {
        string expression = makeExpression(numbers, operators);
        // cout << expression << "\n";
        if(eval(expression) == 0) cout << expression << "\n";
        return;
    }
    

    // DFS
    for(int i=0; i<3; i++) {
        char o = opers[i];

        operators.push_back(o);
        dfs(numbers, operators);
        operators.pop_back();
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> T;
    for(int i=0; i<T; i++) {
        cin >> n;
        vector<int> numbers;
        for(int j=0; j<n; j++) numbers.push_back(j+1);
        vector<char> operators;
        dfs(numbers, operators);
        cout << "\n";
    }

    return 0;
}