BOJ : 1966 프린터 큐

문제 : https://www.acmicpc.net/problem/1966

github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/1966.cpp

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2006 F번

• ACM-ICPC Live Archive
• PKU Judge Online
• TJU Online Judge
• Sphere Online Judge
• HDU Online Judge

입력값이 작아 부르트 포스로 풀 수 있을 것 같지만 디큐를 이용해서 풀어보았다.

#include <iostream>
#include <deque>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        deque<pair<int, bool>> dq;
        int N,M,a,ans=0;
        cin>>N>>M;
        for(int i=0;i<N;i++){
            cin>>a;
            i==M ? dq.push_back(make_pair(a,true)) : dq.push_back(make_pair(a,false));
        }
        while(!dq.empty()){
            int f = dq.front().first;
            bool c = dq.front().second;
            bool flag = false;
            dq.pop_front();
            for(int i=0;i<dq.size();i++){
                if(f < dq.at(i).first) {
                    dq.push_back(make_pair(f, c));
                    flag = true;
                    break;
                }
            }
            if(!flag){
                ans++;
                if(c) break;
            }
        }
        cout<<ans<<"\n";
    }
}