백준 7490 0 만들기 (C++)

7490번: 0 만들기

백트래킹을 이용한 문제이다. dfs를 이용해 4가지 경우의 수를 확인해보며 결과가 0일 경우 저장해주었다. 4가지 경우의 수는 다음과 같다.

• '+' 인 경우
• '+' 다음에 ' ' 인 경우
• '-' 인 경우
• '-' 다음에 ' ' 인 경우

처음 dfs를 돌 때 N은 무조건 3 이상이므로 1과 12로 시작을 해준다. 그 후 dfs를 돌면서 결과를 구한 후 이를 정렬을 해주고 출력해주었다.
어렵지 않게 풀 수 있었다. 다만 첫 dfs를 시작할 때 "1 2"가 아닌 "12"로 시작하여 계속해서 틀렸었다. 이유를 찾는데 시간 낭비가 좀 있었기에 오타를 조심하도록 노력해야겠다.

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

using namespace std;

int T, N;
vector<string> v;

void dfs(int depth, int res, string s) {
    if (depth == N + 1) {
        if (res == 0) v.push_back(s);
        return;
    }

    dfs(depth + 1, res + depth, s + '+' + to_string(depth));
    if (depth <= N - 1)
        dfs(depth + 2, res + (10 * depth + depth + 1), s + '+' + to_string(depth) + ' ' + to_string(depth + 1));

    dfs(depth + 1, res - depth, s + '-' + to_string(depth));
    if (depth <= N - 1)
        dfs(depth + 2, res - (10 * depth + depth + 1), s + '-' + to_string(depth) + ' ' + to_string(depth + 1));
}

void solution() {
    dfs(2, 1, "1");
    dfs(3, 12, "1 2");

    sort(v.begin(), v.end());

    for (auto elem : v) {
        cout << elem << "\n";
    }
    cout << "\n";
}

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

    cin >> T;

    for (int i = 0; i < T; i++) {
        v.clear();

        cin >> N;
        solution();
    }

    return 0;
}