10487 4 thought

 

수학식을 어떻게 깔끔하게 처리하지....

 

중복순열로 모든 경우를 확인했다. 결과마다 식을 미리 저장해두고 식만 미리 뽑아쓰게 계산했다. 

4 - 4- 4 - 4 = ?? 

arr[??] = "4 - 4- 4 - 4 = ??" 요런 식으로

 

그런데 이제 식을 계산하는게 문제였다. 4 * 4 + 4 * 4를 *부터 계산해야 하는데 이걸 어떻게 처리할지 아주 고민이었다. 

결국 *를 먼저 계산해두고 나중에 +-를 계산하도록 했다. 그런데 마음에 들지 않는다.... 다른 사람 코드를 좀 봐야겠다. 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

#define SUM 1000000

string ans[3000000];

void solve(vector<char> perm) {
    
    
    string s = "";
    for(int i = 0; i < perm.size(); i++)
    {
        s += "4 ";
        s += perm[i];
        s += " ";
    }
    s += "4 = ";
    
    // 곱셈 계산용
    stack<string> st;
    st.push("4");
    for(int i = 0; i < perm.size(); i++)
    {
        if (perm[i] == '*') {
            string tmp = st.top();
            st.pop();
            st.push(to_string(stoi(tmp) * 4));
            continue;
        }
        else if (perm[i] == '+')
            st.push("+");
        else if (perm[i] == '-')
            st.push("-");
        else if (perm[i] == '/') {
            string tmp = st.top();
            st.pop();
            st.push(to_string(stoi(tmp) / 4));
            continue;
        }
        st.push("4");
    }
    
    // while(!st.empty()) {
    //     cout << st.top();
    //     st.pop();
    //     cout << endl;
    // }
    
    // 스택 뒤집음....
    stack<string> st2;
    while(!st.empty()) {
        st2.push(st.top());
        st.pop();
    }
    
    
    // 덧셈 계산용
    int res = stoi(st2.top());
    st2.pop();
    while(!st2.empty()) {
        if (st2.top() == "+") {
            st2.pop();
            res += stoi(st2.top());
            st2.pop();
        }
        else if (st2.top() == "-") {
            st2.pop();
            res -= stoi(st2.top());
            st2.pop();
        }
    }
    
    s += to_string(res);
    
    // cout << s << endl;
    
    ans[res + SUM] = s;
}

void repeatPermutation(vector<char> vec, vector<char> perm, int depth)
{
    if (depth == perm.size())
    {
        solve(perm);
        
        return;
    }
    
    for(int i = 0; i < vec.size(); i++)
    {
        perm[depth] = vec[i];
        repeatPermutation(vec, perm, depth + 1);
    }
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    const int r = 3;
    
    vector<char> v = {'*', '+', '-', '/'};
    vector<char> perm(r);
    
    repeatPermutation(v, perm, 0);
    
    
    int m;
    cin >> m;
    
    for (int i = 0; i < m; i++) {
        int n;
        cin >> n;
        
        if (ans[n + SUM] == "") {
            cout << "no solution\n";
            continue;
        }
        
        cout << ans[n + SUM] << "\n";
    }
    
    
    
    return 0;
}