[백준/c++] 2529번: 부등호

 

 

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

2529번: 부등호

 

후.. 처음에는 아 이걸 어떻게 해;; 했었는데 그냥 백 트랙킹으로 순서가 다른 수열을 쭉 늘어놓고 부등호 비교 연산을 하면 된다.ㅋ

2번째 예제를 돌리면서 시간이 좀 걸리길래 시간초과인가 했는데 잘 됐다!^^

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int k;
char ch[10];
vector<string> v;
string s;
bool visit[10];

bool check(){
    for(int i=0; i<k; i++){
        if(ch[i] == '>' && s[i] < s[i+1]) return false;
        if(ch[i] == '<' && s[i] > s[i+1]) return false;
    }
    return true;
}

void backtracking(int cnt){
    if(cnt == k+1){
        if(check()) v.push_back(s);
        return;
    }
    
    for(int i=0; i<10; i++){
        if(!visit[i]){
            visit[i] = true;
            s += to_string(i);
            backtracking(cnt+1);
            s = s.substr(0, s.size()-1);
            visit[i] = false;
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> k;
    for(int i=0; i<k; i++) cin >> ch[i];
    backtracking(0);
    sort(v.begin(), v.end());
    cout << v[v.size()-1] << '\n' << v[0] << '\n';
    return 0;
}