[BOJ 10431 // C++] 줄세우기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 10431번 문제인 줄세우기이다.
문제는 아래 링크를 확인하자.

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

10431번: 줄세우기

기존 줄의 아이들이 키순서대로 서있는 상태라면 새 아이가 규칙에 따라 줄을 서고 난 뒤에도 줄의 아이들이 키순서대로 서있게 된다는 점을 관찰하자. 또한, 초기상태(한 명의 아이가 줄을 서있는 상태)는 아이들이 키순서대로 서있는 상태로 생각할 수 있음을 관찰하자. 이 관찰을 이용하면 줄의 아이들은 항상 키순서대로 서있는 상태가 됨을 알 수 있다.

 

위의 성질을 바탕으로 생각하면, 새 아이가 줄에 들어올 때 뒤로 물러서게 되는 아이들은 정확히 새 아이보다 키가 큰 아이들과 같다는 점을 알 수 있다. 이를 이용해 새 아이를 줄에 추가할 때마다 먼저 들어온 아이들 중 새 아이보다 키가 큰 아이들의 수를 모두 합하는 것으로 문제의 답을 구할 수 있다.

 

아래는 제출한 소스코드이다.

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

int P;

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

	cin >> P;
	while (P--) {
		int T, ans = 0; cin >> T;
		vector<int> vec;
		for (int i = 0; i < 20; i++) {
			int x; cin >> x;
			for (auto& k : vec) {
				if (x < k) ans++;
			}
			vec.emplace_back(x);
		}

		cout << T << ' ' << ans << '\n';
	}
}