[BAEKJOON] 10431번 줄세우기

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

10431번: 줄세우기

1. 자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다.
2. 자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다.

학생들이 뒤로 물러 난 걸음 수?

 

처음에는 정렬이 안될때마다 학생을 직접 집어넣어줘야하는줄 알고 까다롭다고 생각했다.

근데 조금만 생각해보니 위의 조건자체가 정렬을 매번 한다는 의미다. 즉, 오름차순 정렬되지 않은 키가 들어온다면 그때마다 정렬만 해주면 되는거다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int p;
//20명인 애들번호 키 순으로 오름차순 정렬(중복x)
int main() {
	cin >> p;
	while (p--) {
		int t, cnt = 0;
		vector<int> v, res;
		cin >> t;
		for (int i = 0; i < 20; i++) {
			int num;
			cin >> num;
			v.push_back(num);
			for (int i = 0; i < v.size(); i++) {
				if (v[i] > num) {
					cnt += v.size() - i - 1;
					sort(v.begin(), v.end());
					break;
				}
			}
		}
		cout << t << " " << cnt << '\n';
	}
}