[BOJ] 2529번 "부등호" (C++)

브루트포스 문제를 연습해보려고 카테고리에서 고른 문제

 

문제에서 선택된 숫자는 모두 달라야 한다고 해서 숫자의 방문 여부를 표시해주는 bool 배열을 사용하며 재귀로 구현해야겠다고 생각했다

 

근데 난 재귀에 자신이 없다 하하

. 

.

.

 

또, 출력 정수는 문자열이어야 한다고 해서 애초에 답 저장을 vector에 string으로 넣었다 (to_string 함수를 써서)

그리고 0부터 9까지 방문 여부를 확인하며 하나씩 탐색하기 때문에, 이미 ascending order로 정렬되어있을 것이다

 

조건을 만족하는 수면 string에 to_string으로 하나씩 붙여주고,

재귀함수의 파라미터로 답을 저장한 문자열, 지금 몇번째 재귀(?)인지, 바로 전 숫자가 뭔지(비교해야하니까) 넘겨줬다

그런데 정답이 아니었을때 처리나, 문자열을 넘겨주는 상태 등등에서 계속 오류가 나는 것 같았다..

 

엄청나게 고쳐서

 

맞았다~!!

 

근데 다른 사람들 채점 결과랑 비교해보니까

아주 형편없다

하지만 오래 걸려서 풀었기 때문에

브루트포스, 특히 재귀함수 더 공부하고

다시 풀어보거나 다른 아이디어 생각나서 다시 풀어보면

메모리도..

시간도..

줄일수..

있겠지..

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int k;
char info[9];
vector<string> v;
bool visited[10];

void func(string ans,int turn,int before){
    
    if(turn==k+1){
        v.push_back(ans);
        return;
    }
    
    for(int i=0; i<10; i++){
        if(!visited[i]){ //방문된 적 없는 수에 한해서만 가능
            if(info[turn-1]=='<'){
                if(i>before){
                    visited[i]=true;
                    ans+=to_string(i);
                }
                
                else
                    continue;
            }
            
            else if(info[turn-1]=='>'){
                if(i<before){
                    visited[i]=true;
                    ans+=to_string(i);
                }
                else
                    continue;
            }
            
            func(ans,turn+1,i);
            ans.pop_back();
            visited[i]=false;
        }
    }
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    cin>>k;
    
    for(int i=0; i<k; i++)
        cin>>info[i];
    
    for(int i=0; i<10; i++){
        string ans;
        visited[i]=true;
        ans+=to_string(i);
        func(ans,1,i);
        ans.pop_back();
        visited[i]=false;
    }
    
    cout<<v[v.size()-1]<<endl;
    cout<<v[0]<<endl;
}