0 만들기 7490

문제

접근 방법

모든 경우를 확인하면 된다.
N에 도달했을 때 총합이 0이면 수식이 옳다는 것이다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int tc, N;
vector<string> ret;
void dfs(int idx, vector<int> arr, string cal)
{
    if (idx > N)
    {
        int sum = 0;
        for (int i : arr)
            sum += i;
        if (sum == 0)
            ret.push_back(cal);
        return;
    }
    arr.push_back(idx);
    dfs(idx + 1, arr, cal + '+' + char(idx + '0'));
    arr.pop_back();
    arr.push_back(-idx);
    dfs(idx + 1, arr, cal + '-' + char(idx + '0'));
    arr.pop_back();
    int val = arr.back() < 0 ? -idx : idx;
    arr.back() = arr.back() * 10 + val;
    dfs(idx + 1, arr, cal + ' ' + char(idx + '0'));
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> tc;
    for (int i = 0; i < tc; ++i)
    {
        ret.clear();
        cin >> N;
        dfs(2, {1}, "1");
        sort(ret.begin(), ret.end());
        for (string j : ret)
            cout << j << "\n";
        cout << "\n";
    }
    return 0;
}

풀이

공백을 사용한 경우가 우선순위가 높다는 것을 인지하지 못하고
더하기부터 했다가 출력값이 달랐다. 그래서 정렬하는 방식으로 풀었다.
공백->더하기->빼기 순으로 탐색하면 된다.