[백준/알고리즘] 1138번 한 줄로 서기 (실버 2)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 1138번

 

키가 1인 사람부터, 키가 N인 사람까지 N명의 사람이 있다. 각각의 사람들은, 자신의 왼쪽에 있는 사람 중 자신보다 키가 큰 사람의 수를 기억하고 있다. 이때, 사람들이 줄을 선 순서대로 키를 출력하시오.

 

풀이 알고리즘 : 완전탐색

 

사람의 수가 1 <= N <= 10 인 자연수로 주어진다. 즉 최악의 경우 키가 1, 2, 3, ..., 10인 10명의 사람이 순서를 가지고 서있는 경우이다. 이는 모두 탐색했을 때, 10!로, 충분히 완전탐색 할 수 있다.

 

이를 위해 next_permutation 함수를 사용하였다. 초기값을 1,2,3,...,N으로 정렬된 상태로 주고, do-while문을 이용해 현재 순열 상태에서 주어진 정보와 일치하는지 확인하였다. 만약 일치한다면 정답이므로 출력하고 break를 하면 된다. 

 

소스코드 보기

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

// 전역변수
int n;

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

	int n; cin >> n;
	int leftperson[n + 1] = {0};
	int solve[n] = {0};
	for(int i = 1; i <= n; i++) cin >> leftperson[i];
	for(int i = 0; i < n; i++) solve[i] = i + 1;

	do {
		bool ret = true;
		for(int i = 0; i < n; i++) {
			int bigcnt = 0;
			for(int j = 0; j < i; j++) {
				if(solve[i] < solve[j]) bigcnt++;
			}
			if(bigcnt == leftperson[solve[i]]) {
				ret = ret && true;
			} else {
				ret = ret && false;
			}
		}
		if(ret) {
			for(int i = 0; i < n; i++) {
				cout << solve[i] << " ";
			}
			break;
		}
	} while(next_permutation(solve, solve + n));

	return 0;
}