[오답] SWEA 4008: 숫자 만들기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE

연산자의 수가 가령 1,5,0,3

이렇게 주어지면 나는 새로운 벡터에 0을 1개, 1을 5개, 3을 3개 추가하고, 그 백터를 이용해서 순열을 돌렸다.

이 과정에서 중복도 발생하고, set을 사용해서 중복을 처리해주더라도 연산 시간이 소모되기 때문에 시간초과가 나는 것 같다.

따라서, 그냥 1,5,0,3 상태에서, 내가 무언가를 뽑으면 그 원소에 1을 더하거나 빼주고, 양수일 경우에만 뽑을 수 있게 하는 방식으로 DFS를 구현해야 통과할 수 있을 것 같다.

아래는 시간 초과를 받은 코드이다.

#include<vector>
#include<iostream>
#include<set>
#include<climits>
using namespace std;
int n;
long long Min = LONG_MAX;
long long Max = LONG_MAX * -1;
vector<int> opr;
vector<int> arr;
 
set<vector<int> > st;
int num[13];
bool used[13];
 
 
 
void pick(int k) {
    if (k == n - 1) {
        long long res = num[0];
        for (int i = 0; i < arr.size(); i++) {
            int cmd = arr[i];
 
            if (cmd == 0)
                res += num[i + 1];
            else if (cmd == 1)
                res -= num[i + 1];
            else if (cmd == 2)
                res *= num[i + 1];
            else
                res /= num[i + 1];
        }
 
        if (res < Min) Min = res;
        if (res > Max) Max = res;
        //st.insert(arr);
        return;
    }
    
    for (int i = 0; i < opr.size(); i++) {
        if (!used[i]) {
 
            //arr.push_back(opr[i]);
            arr[k] = opr[i];
            used[i] = true;
            pick(k + 1);
            used[i] = false;
            //arr.pop_back();
        }
    }
}
void process() {
 
    for (set<vector<int> > ::iterator itr = st.begin(); itr != st.end(); itr++) {
        vector<int> cur = *itr;
    /*    long long res = num[0];
        for (int i = 0; i < cur.size(); i++) 
            res = cal(res, cur[i], num[i + 1]);*/
        
        long long res = num[0];
        for (int i = 0; i < cur.size(); i++) {
            int cmd = cur[i];
 
            if (cmd == 0)
                res += num[i + 1];
            else if (cmd == 1)
                res -= num[i + 1];
            else if (cmd == 2)
                res *= num[i + 1];
            else 
                res /= num[i + 1];
        }
 
        if (res < Min) Min = res;
        if (res > Max) Max = res;
    }
 
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    
    for (int tc = 1; tc <= T; tc++) {
        cin >> n;
 
        //더하기, 뺴기, 곱하기, 나누기
        for (int i = 0; i < 4; i++) {
            int cnt;
            cin >> cnt;
            while (cnt--) {
                opr.push_back(i);
            }
        }
        for (int i = 0; i < n; i++)
            cin >> num[i];
    
        for (int i = 0; i < n - 1; i++)
            arr.push_back(0);
 
        pick(0);
        //process();
 
        long long dif = Max - Min;
        if (dif < 0) dif *= -1;
        cout << "#" << tc << ' ' << dif << '\n';
 
        Min = LONG_MAX;
        Max = LONG_MAX * -1;
        opr.clear();
        st.clear();
        arr.clear();
    }
    return 0;
}