[2529] 부등호

[2529] 부등호

---

부등호 n개의 배열이 주어지면,

해당 부등호 들을 만족시키는 숫자 n+1개의 배열 중 가장 작은 숫자 배열과 가장 큰 숫자배열을 찾는 문제.

부등호 배열 A = {<, >} 가 주어지면 이를 만족하는 숫자는 0 < 2 > 1 , 1 < 3 > 2 , 2 < 4 > 3, ... , 8 < 9 > 7 과 같다.

이 중 가장 큰 숫자 배열은 897이고, 가장 작은 숫자배열은 021이다.

1) 그냥 다 보기

부등호가 기껏해봐야 9개가 주어지고, 10개의 숫자로 이루어진 배열이므로 최대 10!의 경우를 모두 보면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    int k;
    cin >> k;
    string h, l, a, ms, mns;
    long long mx = 0, mn = 9876543210;
    for(int i = 0; i < k+1; i++){
        h.push_back('9'-k+i);
        l.push_back('0'+i);
    }
    for(int i = 0; i < k; i++){
        char ch; cin >> skipws>> ch;
        a.push_back(ch);
    }
    do{
        bool flg = true;
        for(int i = 0; i < a.size(); i++){
            if(a[i] == '<'){
                if(h[i] > h[i+1]) flg = false;
            }else{
                if(h[i] < h[i+1]) flg = false;
            }
        }
        if(flg){
            long long tmpmx = stoll(h), tmpmn = stoll(l);
            if(mx < tmpmx) {
                mx = tmpmx;
                ms = h;
            }
            if(mn > tmpmn) {
                mn = tmpmn; mns = l;
            }
        }
    }while(next_permutation(h.begin(), h.end()) & next_permutation(l.begin(), l.end()));
    cout << ms << endl;
    cout << mns << endl;
    return 0;
}
 

당연히 시간은 고정적으로 걸리고, 10!의 경우를 모두 다 보는 만큼 걸린다.

2) 좀 더 효율적으로 풀어보자

재귀 적으로 경우의 수를 모두 다 보는 방식으로 바꾸면 훨씬 짧은 시간안에 해결할 수 있다.

작은 숫자의 배열을 찾는 경우 0부터 9까지 넣는 방식으로, 큰 숫자의 배열을 찾는 경우 9부터 0까지 넣는 방식으로 함수를 짜 넣으면 된다.

#include <cstdio>
bool eq[10], set[10], finished;
int a[10], k;
bool isInRule(int idx, int n){
    if(idx == 0) return true;
    else if(eq[idx-1]) return a[idx-1] < n;
    else return a[idx-1] > n;
}
int findAns(int idx, int remain, bool inv){
    if(remain <= 0){
        for(int i = 0; i <= k; i++) printf("%d",a[i]);
        printf("\n");
        finished = true;
        return 0;
    }
    if(!inv){
        for(int i = 9; i >= 0; i--){
            if(isInRule(idx, i) && !set[i]){
                a[idx] = i;
                set[i] = true;
                findAns(idx+1, remain-1, inv);
                if(finished) return 0;
                set[i] = false;
            }
        }
    }
    else {
        for(int i = 0; i < 10; i++){
            if(isInRule(idx, i) && !set[i]){
                a[idx] = i;
                set[i] = true;
                findAns(idx+1, remain-1, inv);
                if(finished) return 0;
                set[i] = false;
            }
        }
    }
    return 0;
}
int main(){
    char ch;
    scanf("%d",&k);
    for(int i = 0; i < k; i++){
        scanf(" %c",&ch);
        if(ch == '<') eq[i] = true;
        else eq[i] = false;
    }
    findAns(0, k+1, false);
    for(int i = 0; i < 10; i++) set[i] = false;
    finished = false;
    findAns(0, k+1, true);
    return 0;
}