[BOJ/C++] 줄세우기(10431번)

1. 개요

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

10431번: 줄세우기

1-1. 설명

초등학교 선생님은 아이들을 데리고 단체로 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키순서대로 번호를 부여한다. 번호 부여시 키가 가장 작은 아이가 1번, 그다음 2번, ... 가장 큰 아이는 20번이 된다. 반 아이들은 항상 20명이며 다행히 같은 키를 가진 학생은 한명도 없으므로 아이들은 번호를 인지하고 한줄로 세우면 제대로 된 위치에 잘 서게 된다. 하지만 반 아이들은 자기가 키 순으로 몇번째인지 잘 알지못해 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 특별한 방법을 생각했다.

우선 아무나 한명을 뽑아 맨 앞에 세운다. 그리고 그 다음부터 학생이 한명씩 줄의 맨뒤에 서면서 다음 과정을 거친다

 - 자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝남

 - 자기 앞에 자기보다 키큰 학생이 한명이상 있다면 그중 가장앞에있는 학생(A)의 바로앞에 섬. 이때, A부터 그 뒤 모든 학생들은 공간을 만들기 위해 한발씩 뒤로 물러서게 됨

이 과정을 반복하면 오름 차순으로 줄을 설 수 있다. 아이들의 키가 주어지고, 어떤 순서로 아이들이 줄서기를 할지 주어진다. 위의 방법을 마지막 학생까지 시행해 줄서기가 끝났을 때 학생들이 총 몇번 뒤로 물러서게 되는지 결과를 출력하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫줄에 테스트 케이스의 수 P가 주어지며, P는 1 이상 1,000 이하

 - 각 테스트 케이스는 번호 T와 20개 양의 정수가 공백으로 주어짐

---

2. 구현

2-1. 풀이

for문을 통해 현재 값을 뒤에값과 비교하면서 뒤엣값이 더 작으면 앞으로 옮겨야하는 숫자이므로 +1 해주었다. 문제를 보고 단순하게 구현해내면 된다. 

2-2. 코드

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

int students[20];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int P, num, result = 0;
    cin >> P;

    for (int tc = 0; tc < P; tc++) {
        cin >> num;
        result = 0;
        for (int i = 0; i < 20; i++) cin >> students[i];
        for (int i = 0; i < 20; i++) {
            for (int j = i; j < 20; j++) {
                if (students[i] > students[j]) result += 1;
            }
        }
        cout << num << ' ' << result << "\n";
    }

    return 0;
}