백준-부등호 : 2529번

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

2529번: 부등호

문제의 조건이 순서만 변경할 수 있을 때는 순열을 사용하면 됩니다.

부등호 앞에 그리고 뒤에 한 자리 숫자를 나와서 모든 부등호의 관계를 만족시키려고 합니다

하지만 이때 선택한 수가 같으면 안 됨.

 

문제의 가장 중요한 조건 중에 하나는 선택할 숫자는 한자리숫자 이고 선택한 숫자가 같은면 안된다.

즉, 순서 문제가 된다.

예를 들어, 0부터 9까지 소중해서 일정 4개를 골랐다고 해봅시다. 그럼 9,8,7,6 을 선택해서, 중복없이 순서대로 나열하고, 부등호가 성립되는지 확인하면된다.

 

<전체 경우의 수>

10개의 수중에 K+1개를 고른다 = 2^(k+1)  --> 필요없음.

이 K+1개의 수에 대해서 순서를 정한다. = !(K+1)

부등호가 성립하는 검사 = K+1

결론 : 2^10 * 10! * 10 = 1024 * 3628800*10 (OMG)

 

자~!! 시간복잡도를 줄여 봅시다.

가장큰수와 가장작은수를 찾는 것임으로, K+1이 4개라면,

큰수는 9,8,7,6 작은수는 0,1,2,3 을 선택하면 된다.

즉, 위 시간복잡도에서 2^(K+1)이 없어지게 된다.

 

#include <bits/stdc++.h>
using namespace std;
bool check(vector<int>& perm, vector<char>& a);

int main() {
    int k;
    cin >> k;
    vector<char> a(k);
    vector<int> min(k + 1);
    vector<int> max(k + 1);
    for (int i = 0; i < k; i++) {
        cin >> a[i];
    }

    for (int i = 0; i <= k; i++) {
        min[i] = i;
        max[i] = 9 - i;
    }
    do {
        if (check(min, a)) {
            break;
        }
    } while (next_permutation(min.begin(), min.end()));
    do {
        if (check(max, a)) {
            break;
        }
    } while (prev_permutation(max.begin(), max.end()));
    for (int i = 0; i < max.size(); i++) {
        cout << max[i];
    }
    cout << '\n';
    for (int i = 0; i < min.size(); i++) {
        cout << min[i];
    }
    cout << '\n';
    return 0;
}

bool check(vector<int>& perm, vector<char>& a) {
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == '<' && perm[i] > perm[i + 1]) {
            return false;
        }
        if (a[i] == '>' && perm[i] < perm[i + 1]) {
            return false;
        }
    }
    return true;
}