[1138번] 한 줄로 서기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Permutation :: http://www.crocus.co.kr/306

2. 부르트 포스

사실상 이 문제는 N의 최대가 10이기에, 10!로 모든 경우를 다따져서 해결 할 수 있다.

위의 Permutation 링크에서 순열 코드를 이용하여 그대로 쓴 후, 그 내부인 k == m에서 자신보다 앞에 몇명이 존재하는지

for문을 통해 체크해주고 한번이라도 틀리면 break로 중지하고 다른 순열을 확인하면 된다.

10!에 내부 for문까지해서 O(10*10!) = 36,288,000이기에 무난하게 통과한다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
pii arr[51];
 
int cnt = 0;
 
void permutations(pii *a, const int k, const int m)
{
    int i;
    int temp;
 
 
    if (k == m) //순열이 완성됐을 때 한 줄로 서기 검사
    {
        bool chk = false;
        for (i = 0; i <= m; i++)
        {
            int front = 0;
            for (int j = i - 1; j >= 0; j--)
                if (a[i].first < a[j].first)
                    front++;                    
 
            if (front == a[i].second)
                chk = true;
            else
            {
                chk = false;
                break;
            }
        }
        if (chk)
        {
            for (int i = 0; i <= m; i++)
                printf("%d ", a[i].first);
            exit(0);
        }
    }
 
    else 
    {
        for (i = k; i <= m; i++)
        {
            swap(a[k], a[i]); 
            permutations(a, k + 1, m);                                       
            swap(a[k], a[i]);
        }
 
    }
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
        arr[i] = { i + 1, val };
    }
 
    permutations(arr, 0, n - 1); // 0~n-1 까지의 수는 총 n가지이다. 
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>