회전하는 큐

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

1021번: 회전하는 큐

#include <iostream>
#include <vector>
#include <deque>
 
using namespace std;
 
deque<int> q;
int n, m;
int ans =987654321;
vector<int> ch;
 
void go(deque<int>& q, int idx, int cnt){
    if(cnt > ans){
        return;
    }
    if(idx == m){
        if(ans > cnt) ans = cnt;
        return;
    }
    else{
        if(q.front() == ch[idx]){
            int x = q.front();
            q.pop_front();
            go(q, idx+1, cnt);
            q.push_front(x);
        }
        else{
            deque<int> q1 = q;
            vector<int> v;
            int id = 0;
            while(!q1.empty()){
                if(ch[idx] == q1.front()) id = v.size();
                v.push_back(q1.front());
                q1.pop_front();
            }
            int x = q.front();
            if(id <= q.size()/2) {
                q.pop_front();
                q.push_back(x);
                go(q, idx, cnt + 1);
                q.pop_back();
                q.push_front(x);
            }
            else {
                x = q.back();
                q.pop_back();
                q.push_front(x);
                go(q, idx, cnt + 1);
                q.pop_front();
                q.push_back(x);
            }
        }
    }
 
 
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        q.push_back(i);
    }
    for(int i = 0; i < m; i++){
        int c;
        cin>>c;
        ch.push_back(c);
    }
    deque<int> q1 = q;
    go(q,0,0);
    cout<<ans<<'\n';
    return 0;
}

시뮬레이션 이라기 보다는 브루트포스문제가 아닐까싶은문제였다.

일단 백트래킹같은 방식으로는 진행시 걸러줄 조건을 찾기는 조금 까다로웠고

queue 나 deque에 넣으면 안을볼수없다는 불편함때문에 그냥 벡터에 deque의 원소 복사한것들을

하나하나 넣어가면서 위치파악하고 액션취해줄것을 선택해서 진행했다.