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

문제 설명

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

 

 

접근 방법 - 값 비교를 활용한 정렬 응용문제

백준의 10431번 문제는 값 비교 연산을 활용하여 비교적 어렵지 않게 해결할 수 있는 정렬 응용문제이다.

해당 문제는, 줄을 세울 20명의 아이들의 키가 입력으로 주어질 때 한 명씩 줄을 세우면서 아이들이 뒤로 물러나는 총 횟수를 연산하여 출력해야 하는 문제이다.

아이들의 키를 기준으로 오름차순으로 한 줄로 세우고자 한다. 이를 위해서, 아이들을 한 명씩 차례대로 줄에 세우면서 오름차순 정렬을 진행하고자 한다.

이때, 현재 순번의 아이를 줄에 세울 때, 이미 줄을 서 있는 아이들 중에서 키가 더 큰 아이가 있다면 그 아이들은 모두 한 걸음씩 뒤로 물러난다. 그리고 그 자리에 현재 순번의 아이가 들어가 서도록 할 예정이다.

보다 구체적인 설명은 문제의 본문을 참고하길 바란다.

 

필자는 입력을 하나씩 받으면서, 그 입력값보다 큰 값이 앞에 있던 경우를 모두 카운팅 하여 이를 정답으로 출력하도록 하였다.

이전의 입력값들이 값 비교 연산에 연이어 활용되기 때문에, 배열에 입력값들을 하나씩 저장하게끔 하였다.

보다 자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 테스트 케이스의 수(t)를 입력받는다.

 

2) t의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다.

- 테스트 케이스의 번호(n)를 입력받는다.

- 아이들의 키 정보를 저장할 임의의 배열 arr를 20의 크기로 미리 선언해 둔다.

이에 더불어, 아이들이 뒤로 물러나는 총 횟수를 저장할 변수 sum을 0으로 초기화하여 미리 선언해 둔다.

- 다른 반복문을 활용하여, 20명의 아이들의 키 정보를 하나씩 입력받으며 아래의 연산을 취한다.

- 현재 순번(j)의 아이보다 큰 키를 가진 아이들의 수를 저장할 임의의 변수 big을 0으로 초기화하여 선언해 둔다.
- 현재까지 저장된 arr의 값들을 탐색하며 현재 순번의 아이의 키(arr[j])와 값을 비교한다.
만약 키가 더 큰 아이를 발견하였다면, 이 아이는 한 걸음 뒤로 물러나야 하기 때문에 앞서 선언한  big 값에 1을 가산하도록 한다.
- 위에서 연산이 완료된 big의 값을 sum에 더한 뒤 다음 연산을 진행한다.

- 위 연산이 모두 완료되었다면, 현재 테스트 케이스에 대하여 n값과 최종적으로 저장된 sum 값을 정답으로 출력한다.

 

3) 모든 테스트 케이스에 대한 정답을 출력하였다면, 실행을 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 10431번 코드
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n;  cin >> n;
        int arr[20];
        int sum = 0;
        for (int j = 0; j < 20; j++) {
            cin >> arr[j];
            if (j != 0) {
                int big = 0;
                for (int k = 0; k < j; k++) {
                    if (arr[k] > arr[j]) { big++; }
                }
                sum += big;
            }
        }
        cout << n << " " << sum << endl;
    }
}

 

제출 결과

(2022.08.20 백준 10431번 문제 제출 결과)