백준 7490 , 0 만들기, 문자열수식 백트래킹,

문제

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

풀이

• 이런 문제의 경우 수식과, 숫자를 분리해야한다는 것을 깨달았다.

• back(int cnt) 는 현재 cnt개의 수식을 선택했다의 의미이다. 수식은 숫자보다 하나 더 작다.

• calc()

  • 계산할때 까다로운 부분이 곱하기이다 그래서 곱하기 연산은 따로 미리 처리해서 다시 숫자랑 문자를 분리해서 이후에 계산을 한다

• Trans()

  • 간단하다 현재 숫자와 문자를 분리한 것을 뭉쳐서 문자열로 만드는 부분이다.

틀린이유

• 처음에는 간단하게 +, -, 공백을 각각 back을 호출해서 작동하였다 그렇지만 틀렸다 이유는 곱하기는 우선순위가 있기때문이다.

• 이 처리를 위해서 아예 방법을 싹 바꿨다...

소스

#include <bits/stdc++.h>

using namespace std;

char oper[3] = { '+', '-', ' ' };
vector<char> op;
vector<int> nums;
vector<string> ans;

int n, t;

string Trans() {
    string s;
    s = to_string(nums[0]);

    for (int i = 0; i < op.size(); i++)
    {
        s += op[i];
        s += to_string(nums[i + 1]);
    }
    return s;
}

int Calc() {

    //숫자와 연산을 나눠놓고, 곱하기 부분을 미리 처리 해 놓고 나머지 더하기 빼기 처리 
    vector<char> tmpOp;
    vector<int> tmpNum;

    string tmp = to_string(nums[0]);
    for (int i = 0; i < op.size(); i++)
    {
        if (op[i] == ' ') {
            tmp += to_string(nums[i + 1]);
        }
        else {
            tmpNum.push_back(stoi(tmp));
            tmp = "";
            tmp += to_string(nums[i + 1]);
            tmpOp.push_back(op[i]);
        }

        if (i == op.size() - 1) {
            tmpNum.push_back(stoi(tmp));
        }
    }

    int Ans = tmpNum[0];
    for (int i = 0; i < tmpOp.size(); i++) {
        if (tmpOp[i] == '+') {
            Ans += tmpNum[i + 1];
        }
        else if (tmpOp[i] == '-') {
            Ans -= tmpNum[i + 1];
        }
    }
    return Ans;
}

void back(int cnt) {
    if (cnt == n - 1) {
        if (Calc() == 0) {
            ans.push_back(Trans());
        }
        return;
    }

    for (int i = 0; i < 3; i++)
    {
        op.push_back(oper[i]);
        back(cnt + 1);
        op.pop_back();
    }
}
int main() {


    cin >> t;
    while (t--)
    {
        op.clear();
        nums.clear();
        ans.clear();

        cin >> n;
        for (int i = 0; i < n; i++) nums.push_back(i + 1);

        back(0);

        sort(ans.begin(), ans.end());
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i] << endl;
        }
        cout << endl;
    }
    return 0;
}