[C++] BOJ-2529

 

문제풀이

---

1. 재귀함수로 모든 경우의 수를 탐색해서 부등호의 조건에 맞는 수열을 찾는다.

 

2. k가 0일 경우를 제외하고 수열의 k-1번째 요소와 현재 들어갈 숫자를 비교해서 부등호의 조건에 맞다면 수열에 집어넣는다.

 

3. 제일 마지막에 저장된 수열과 제일 처음 저장된 수열을 출력한다.

 

4. 재귀함수를 통해 0부터 차근차근 탐색하기 때문에 처음과 마지막에 저장된 수열을 그대로 출력해도 답이 나온다.

 

 

57분 49초

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N , cnt = 0;
char arr[9] = {};
 
vector<int> v[362880];
 
void func(int k, int p, bool* ck, int* t_arr){
    if(k == N+1){
        for(int i = 0; i<N+1; i++){
            v[cnt].push_back(t_arr[i]);
        }
        cnt++;
        return ;
    }
    
    for(int i = 0; i<10; i++){
        if(!ck[i]){
            if(k == 0){
                ck[i] = 1;
                t_arr[k] = i;
                func(k+1,p, ck, t_arr);
                ck[i] = 0;
            }else{
                if(arr[p] == '>'){
                    if(t_arr[k-1] > i){
                        ck[i] = 1;
                        t_arr[k] = i;
                        func(k+1,p+1 , ck, t_arr);
                        ck[i] = 0;
                    }
                }else{
                    if(t_arr[k-1] < i){
                        ck[i] = 1;
                        t_arr[k] = i;
                        func(k+1,p+1,ck, t_arr);
                        ck[i] = 0;
                    }
                }
            }
        }
    }
    return ;
}
 
int main(){
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    bool ck[10] = {};
    int t_arr[10] = {};
    for(int i = 0; i<N; i++){
        cin >> arr[i];
    }
    
    func(0,0,ck, t_arr);
    
    for(int i = 0; i<N+1; i++){
        cout << v[cnt-1][i];
    }
    
    cout << "\n";
    
    for(int i = 0; i<N+1; i++){
        cout << v[0][i];
    }
}