1138 - 한 줄로 서기

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

1138번: 한 줄로 서기

과정

1. 만약 앞에 최소 2명의 큰 사람이 있다면 인덱스를 0부터 시작할 필요가 없다.
2. 큰 사람의 수에서 인덱스를 시작하자
3. 하나씩 넣어가며 dfs를 돌리고 조건을 만족하면 종료하자

코드

#include<iostream>

using namespace std;

int N;
int jul[11];
int arr[11];

void input(){
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>arr[i];
    }
}

bool dfs(int now){
    if(now == N){
        for(int i=0;i<N;++i){
            int cnt = 0;
            int node = i+1;

            for(int j=0;jul[j]!=node;++j)
                if(jul[j] > node)
                    ++cnt;

            if(cnt != arr[node-1])
                return false;
        }

        return true;
    }
        
    for(int i=arr[now];i<N;++i){
        if(jul[i]==0){
            jul[i] = now+1;
            if(dfs(now+1))
                return true;
            jul[i] = 0;
        }
    }


    return false;
}

void solution(){
    dfs(0);
    
    for(int i=0;i<N;++i)
        cout<<jul[i]<<" ";
}

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

    input();
    solution();

    return 0;
}