10431 - 줄 세우기

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

10431번: 줄세우기

생각해 보기

• 3번째 서있던 친구가 맨 앞으로 가게되면 그 사이에 있던 친구들만 움직이면 된다.
• 모든 친구들에 대하여 키가 큰지 비교할 필요 없이 맨 앞에서부터 큰 친구를 만날때까지 비교하면 된다.

코드

#include<iostream>
#include<vector>

using namespace std;

int N;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>N;
    for(int i=1;i<=N;++i){
        vector<int> children(20);

        int tmp, cnt=0;
        cin>>tmp;
        for(int j=0;j<20;++j)
            cin>>children[j];

        for(int j=0;j<20;++j){
            for(int k=0;k<j;++k){
                if(children[k]>children[j]){
                    cnt+=j-k;
                    tmp = children[j];
                    children.insert(children.begin()+k,tmp);
                    children.erase(children.begin()+j+1);
                    break;
                }
            }
        }

        cout<<i<<" "<<cnt<<'\n';
    }

    return 0;
}