[코딩테스트] 백준 10431 줄세우기 | C++

백준 10431 줄세우기

문제 링크

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

문제 요약

학생 20명이 한 명씩 줄의 맨 뒤에 서되, 자기 앞에 자신보다 큰 학생이 있으면 그중 가장 앞 학생 A의 바로 앞에 끼어든다. A부터 뒤 학생들은 한 칸씩 뒤로 물러남
모든 학생이 다 선 뒤, 뒤로 물러난 총 걸음 수를 구한다.

입력

• 첫 줄: 테스트 케이스 수 P (≤ 1000)
• 각 테스트: 테스트 번호 T와 20명의 키(밀리미터, 모두 서로 다름), 줄서기 입장 순서로 주어짐

출력

• 각 테스트마다 T와 총 이동(뒤로 한 칸 물러남) 수를 공백으로 출력

문제 분석

자기 앞에 자신보다 큰 학생이 있으면 한 칸씩 뒤로 물러날 때

Case 1) 이미 모든 학생 오름차순인 경우

• 학생이 뒤에 설때마다 맞는 위치이기 때문에 뒤로 물러나는 경우 없음 -> 0

Case 2) 만약 오름차순이 아닌 경우

• 우선 쉬운 예시로 903 901 902 순으로 있다고 해보자. 903 친구가 서고 나서 901친구는 903의 뒤에 우선 선 뒤, 901의 앞으로 이동한다. 즉, 한 번의 이동 존재. 그럼 현재 상태 [901 903] 에서 902 친구가 가장 뒤에 서있다가 903의 앞으로 이동한다. 그러면, 두 번의 이동 존재이며 현재 상태 [901 902 903]이다.
• 예시 하나를 더 살펴보자. 905 904 903 902 901 의 순서이다. 905 서고, 904는 905의 앞으로 이동하므로 한 번의 이동 존재. [904 905] 현재 상태에서 903 친구가 904 앞으로 가므로 904 905가 뒤로 한칸씩 이동. 즉, 총 세 번의 이동 존재(기존 한 번 + 이번에 두 번). 현재 상태 [903 904 905] 에서 902 친구가 903의 앞으로 가므로 903 904 905 가 한 칸씩 이동하므로 총 6번의 이동 존재(기존 3번+이번에 3번) 다음으로 901이 902 903 904 905의 앞으로 이동해야하므로 4+6= 총 10번의 이동 존재(기존 6번+이번에4번)

위 예시들에서 일반화를 하자면 현재 순서가 i번째 일 때 i의 전에 있던 사람들 중 i보다 키 큰 사람의 수만큼 이동한다.
예를 들어 두 번째 예시에서 현재 904라면 1번, 현재 903일 때 2번, 현재 902일 때 3번, 901일 때 4번 = 10번이다.
첫 번째 예시에서는 903일 때 0번, 901일 때 1번, 902일 때 1번 = 2번이다.

20번 밖에 안되므로 for문을 20번 돌고 그 안에 이중 포문으로 현재 i일때 i 이전 순서들을 체크하면서 역순서인 경우를 카운트하면 된다.

알고리즘 분류

• 시뮬레이션 + 브루트포스 + 정렬

코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int p;
    cin >> p;

    while (p--) {
        int t;
        int cnt = 0;
        cin >> t;
        
        int students[20];
        for (int i=0; i<20; i++) {
            cin >> students[i];
        }

        for (int i=0; i < 20; i++) {
            for (int j=0; j<i; j++) {
                if (students[i] < students[j]) {
                    cnt++;
                }
            }
        }

        cout << t << ' ' << cnt << '\n';
    }
}