모든 버스의 경우의 수에서 순열, 조합으로 뽑아서 문제를 풀었습니다.

//통근 버스 출발 순서 결정하기
/*
3
3 1 2
출력예제1
0
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

//globals
vector<int> graph;
bool visited[5001];
int N;
int results;

//methods
void Input(){
    
    cin>>N;
    
    for(int i=0; i<N; i++){
        int tmp;
        cin>>tmp;
        graph.push_back(tmp);
    }
    //
}

bool check_bus(vector<int>& tmp_graph){
    if(tmp_graph[0]<tmp_graph[1] && tmp_graph[0]> tmp_graph[2]) return false;
    return true;
}

void prt_combi() {
    vector<int> tmp_graph;
    for (int i = 0; i < N; i++) {
        if (visited[i]) {
           tmp_graph.push_back(graph[i]);
        }
    }
    if(!check_bus(tmp_graph)) results++;
}

void dfs_combi(int idx, int cnt) {
    if (cnt == 3) {
        prt_combi();
        return;
    }
    for (int i = idx; i < N; i++) {
        if (visited[i] == true) continue;
        visited[i] = true;
        dfs_combi(i, cnt + 1);
        visited[i] = false;
    }
}

int Combination(){

    int cnt=0;
    vector<bool> visited(N,false);
    
    for(int i=0; i<3; i++){
        visited[i]=true;
    }
    sort(visited.begin(), visited.end());
    do{
        vector<int> tmp_graph;
        for(int i=0; i<graph.size(); i++){
            if(visited[i]){
                tmp_graph.push_back(graph[i]);
            }
        }

        if(!check_bus(tmp_graph)) cnt++;
    }while(next_permutation(visited.begin(), visited.end()));

    return cnt;
}

void Start(){
    
    dfs_combi(0,0);
    cout<<results<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    
    Start();
    return 0;
}

c++의 next_permutation라이브러리를 사용하여 진행했지만, n이 3에서 5000이하라 시간초과가 발생했습니다.

따라서, DFS를 이용하여 조합을 구현하여 진행했는데도 시간초과가 발생했습니다.

혹시 더 좋은 아이디어 있을까요?