[Silver V] 10431 - 줄세우기

 

[문제 위치]

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

 

[문제 풀이]

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int P; // 테스트 케이스 수
    cin >> P;

    for (int i = 0; i < P; i++) {
        int T; // 테스트 케이스 번호
        cin >> T;

        vector<int> heights(20); // 학생들의 키를 저장
        for (int j = 0; j < 20; j++) {
            cin >> heights[j];
        }

        int steps = 0; // 총 물러선 걸음 수

        vector<int> line; // 현재 줄 서있는 상태
        for (int h : heights) {
            // h를 적절한 위치에 삽입
            int position = line.size();
            for (int k = 0; k < line.size(); k++) {
                if (line[k] > h) {
                    position = k; // h가 들어가야 할 위치
                    break;
                }
            }
            steps += line.size() - position; // 뒤로 물러선 학생들의 수
            line.insert(line.begin() + position, h); // h를 삽입
        }

        // 결과 출력
        cout << T << " " << steps << endl;
    }

    return 0;
}