[BOJ-1138] 한 줄로 서기

백준 1138 한 줄로 서기

 

1138번: 한 줄로 서기

 

문제 설명

 

 - N명의 사람들은 매일 아침 한 줄로 선다.

 

 - 이 사람들은 오민식의 지시대로 선다.

 

 - 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다.

 

 - N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

 

 - 각 사람들이 기억하는 정보가 주어질 때, 줄을 선 순서대로 출력하라.

 

---

 

입력 값

 

 - 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다.

 

 - 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명 있는지 주어진다.

 

 - i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다.

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제에서 전체 사람의 수 N은 10보다 작거나 같은 자연수이다.

 

 - 최대 10명이 줄을 서는 경우의 수는 10! = 3628800 이다.

   360만은 제한 조건 안에 수행할 수 있기 때문에 모든 경우를 살펴볼 수 있다.

 

 - 즉, 모든 사람이 서는 경우의 수를 모두 살펴보고, 해당 순서가 맞는지 판단하면 된다.

 

 

---

 

 

소스 코드

#include <bits/stdc++.h>
#include<unordered_set>

using namespace std;

int leftHeights[11];


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

	int N,n;

	vector<int> arr;

	cin >> N;

	for (int i = 0; i < N; i++) {
		arr.push_back(i);
		cin >> n;
		leftHeights[i] = n;
	}

	do {
		bool isOrder = true;
		for (int i = 0; i < N&&isOrder; i++) {
			int sum = 0;
			for (int j = 0; j < i; j++) {
				if (arr[i] < arr[j]) {
					sum++;
				}
			}
			if (sum != leftHeights[arr[i]]) {
				isOrder = false;
			}
		}

		if (isOrder) {
			for (int i = 0; i < N; i++) {
				cout << arr[i] + 1 << " ";
			}
			cout << endl;
		}
	} while (next_permutation(arr.begin(), arr.end()));


	return 0;
}