[BOJ/백준][Silver2] 1138 : 한 줄로 서기 (C++)

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

1138번: 한 줄로 서기

 

 

[난이도] Silver2
[유형] 브루트포스

[풀이]
N 제한이 10밖에 되지 않기 때문에 v[N] 배열에 1부터 N까지 순서대로 저장 한 뒤
순열을 이용해 정답이 될 수 있는 모든 경우의 수를 만들어 보며 조건을 만족하지는지 체크해주면 됩니다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,a[11],v[11];
bool check(){
    for(int i=1;i<=N;i++){
        int cnt=0;
        for(int j=1;j<i;j++){
            if(v[j]>v[i]) cnt++;
        }
        if(a[v[i]] != cnt) return 0;
    }
    return 1;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        scanf("%d",&a[i]);
        v[i]=i;
    }
    do{
    }while(!check() &&next_permutation(v+1,v+1+N));
    for(int i=1;i<=N;i++) printf("%d ",v[i]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/1138.cpp