[ 백준 BOJ ] 1138번 - 한 줄로 서기 (C++)

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

 

생각 흐름

• N의 최댓값은 10으로 완전 탐색을 돌려도 충분히 시간 안에 풀릴 거 같았다.
• 이 때 시간을 줄여보고자 dfs 돌 때마다 조건에 만족하는지 체크해줬다.

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> v;
bool checked[10];
vector<int> answer;
bool isEnd;

void dfs(vector<int> order, int depth){
    if(isEnd){
        return;
    }
    for(int i = 0; i<order.size(); i++){
        int sum = 0;
        for(int j = 0; j<i; j++){
            if(order[j]>order[i]){
                sum++;
            }
        }
        if(sum!=v[order[i]]) return;
    }
    
    if(depth==N){
        answer = order;
        isEnd=true;
        
        return;
    }
    
    for(int i = 0; i<N; i++){
        if(checked[i]) continue;
        if(isEnd) return;
        
        checked[i] = true;
        order.push_back(i);
        dfs(order, depth+1);
        checked[i] = false;
        order.pop_back();
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N;
    for(int i = 0; i<N; i++){
        int tmp;
        cin>>tmp;
        
        v.push_back(tmp);
    }
    
    dfs(answer, 0);
    
    for(int i = 0; i<N; i++){
        cout<<answer[i]+1<<" ";
    }
    cout<<endl;

    return 0;
}