[C++] 백준 10431: 줄세우기

문제

[C++] 백준 10431: 줄세우기 SILVER 5
https://www.acmicpc.net/problem/10431

 

---

 

접근 방법

이 문제는 학생들의 키를 앞에서부터 한 명씩 줄 세울 때,
뒤로 물러나는 횟수(이동 횟수)의 총합을 구하는 구현 문제이다.

 

학생을 한 명씩 입력받으면서, 현재까지 정렬된 줄(students)에 올바른 위치에 삽입하는 방식으로 시뮬레이션했다.

• 현재 학생 키 now를 받으면
• 앞에서부터 탐색하며 now보다 큰 키를 처음 만나는 위치 j를 찾고
• 그 위치 뒤의 학생들을 한 칸씩 밀어 공간을 만든 뒤 now를 삽입한다
• 이때 밀린 횟수는 (i - j)만큼이므로, 이를 누적해 cnt에 더한다

만약 끝까지 탐색해도 더 큰 값이 없다면, 맨 뒤에 그대로 붙이면 된다.

 

구현 시 주의할 점

• 앞에서부터 탐색하다가 더 큰 값을 찾는 순간 그 위치에 삽입 처리를 하고,
  같은 학생에 대해 불필요하게 더 탐색하지 않도록 반드시 break로 종료해야 한다.
• 삽입 시에는 뒤에서부터 값을 옮겨야 덮어쓰지 않으므로, z = i부터 j까지 역순으로 한 칸씩 밀어준다.

 

---

 

코드

#include <iostream>
using namespace std;

int students[20];

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

	int p = 0;
	cin >> p;

	for (int test_case = 1; test_case <= p; test_case++)
	{
		cin >> test_case;
		
		int cnt = 0;
		for (int i = 0; i < 20; i++)
		{
			int now = 0;
			cin >> now;

			bool flag = false;
			for (int j = 0; j < i; j++)
			{
				if (students[j] > now)
				{
					for (int z = i; z >= j; z--)
						students[z + 1] = students[z];

					students[j] = now;

					cnt += (i - j);

					flag = true;

					break;
				}
			}
			if (flag == false)
				students[i] = now;
		}
		cout << test_case << ' ' << cnt << '\n';
	}
	return 0;
}