[백준/BOJ] 2529 부등호

문제 : 2529 부등호

2529번: 부등호

부등호 기호가 나열되어있는 배열이 주어질 때,

서로 다른 한 자릿수 숫자를 넣어 만족하는 가장 큰 수와

가장 작은 수를 찾아 출력하는 문제이다.

백트래킹 기법을 활용해서 모든 경우의 수를 확인해서 비교하면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e15+7
using namespace std;
ll N, visited[10], mn=INF, mx=-1;
vector<char> arr;
void backtrack(ll now, ll depth){
    if (depth==N+1){
        mx=max(mx,now);
        mn=min(mn,now);
        return ;
    }
    for (int i=0;i<=9;i++){
        if (visited[i]==0){
            if (depth==0 || (arr[depth-1]=='>' && now%10>i) || (arr[depth-1]=='<' && now%10<i)){
                visited[i]=1;
                now=now*10+i;
                backtrack(now, depth+1);
                now/=10;
                visited[i]=0;
            }
        }
    }
}
int main(){
    cin >> N;
    for (int i=0;i<N;i++){
        char a;
        cin >> a;
        arr.push_back(a);
    }
    backtrack(0,0);
    cout << mx << "\n";
    if (pow(10,N)>mn)
        cout << "0";
    cout << mn;
    return 0;
}