[백준] 부등호

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

2529번: 부등호

우선 문제부터 간단하게 요약하면, 

 

부등호 k개가 주어지면, 해당 부등호 사이 사이에 0~9 사이의 숫자를 넣어 부등호 관계가 성립하도록 하는 최대 정수와 최소 정수를 구해야 하는 문제입니다. 

 

<Soltuion>

최대와 최소를 구해야 하므로, 숫자를 어떻게 뽑아도 무조건 만족하는 것이 있을 것이기 때문에 최대는 9부터 감소시키면서 총 k+1개의 숫자로, 최소는 0부터 증가시키면서 k+1개의 숫자를 사용하여 구하면 되는 것을 알 수 있습니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int k;

/*function which checks order is correct*/
bool check(vector<int> &permut, vector<char> &c){
    for(int i = 0; i < c.size(); i++){
        if(c[i] == '<' && permut[i] > permut[i+1]){
            return false;
        }
        if(c[i] == '>' && permut[i] < permut[i+1]){
            return false;
        }
    }
    return true;
}

int main(){
    // get input
    cin >> k;

    vector<char> c(k); // make vector of size k
    for(int i = 0; i<k; i++){
        cin >> c[i];
    }

    vector<int> small(k+1);
    vector<int> big(k+1);

    // fill vector values
    for(int i = 0; i<k+1; i++){
        big[i] = 9-i;
        small[i] = i;
    }

    // find big
    do{
        if(check(big, c)) break; // if find stop
    }while(prev_permutation(big.begin(), big.end()));
    // find small
    do{
        if(check(small, c)) break; // if find stop
    }while(next_permutation(small.begin(), small.end()));

    // print answer
    for(auto &k: big){
        cout << k;
    }
    cout << '\n';
    for(auto &k: small){
        cout << k;
    }
    cout << endl;

    return 0;
}