[백준 - 2529] 부등호 [C++]

1. 문제

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

2529번: 부등호

2. 풀이과정 

1. 부등호의 개수인 k보다 하나 많은 k+1개의 수를 나열한다.

2. 나열된 수들이 주어진 부등호 관계들을 만족하는지 판별한다. 

3. 만족하면 결과 벡터에 저장한다. 

 

[코드설명]

dfs함수는 k+1개의 수들을 나열한다.

k=2이라면, 

0 1 2

0 1 3

0 1 4

    .

    .

7 8 9

와 같은 순서로 수를 나열한다.

 

check함수는 나열된 수들이 입력받은 부등호관계를 만족하는 지 여부를 판별한다.

 

make_string함수는 벡터에 저장되어있는 정수들을 합쳐 문자열로 만든다.

v = { 0, 1, 2} 이면,

make_string은 "012"를 반환한다.

문자열로 만드는 이유는 첫 자리가 0인 경우에 0을 붙여 출력해야하는데, 이를 편하게 하기 위함이다.

 

전체적인 흐름은 dfs함수에서 k+1개의 수를 나열한 후,

check함수를 통해 부등호관계를 만족하는지 판별하고, 

만족한다면 결과 벡터에 문자열 형식으로 저장하여

최대와 최소를 출력해준다.

 

수를 생성할 때, 사전순으로 생성하므로

결과 벡터의 마지막 원소가 최대, 첫 번째 원소가 최소가 된다.

 

3. 코드

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

using namespace std;
int k;
vector<char> arr;
bool visited[10];
vector<string> results;

string make_string(vector<int>& v) {
    string tmp = "";
    for(int i=0; i<k+1; i++) tmp += to_string(v[i]);
    return tmp;
}

bool check(vector<int>& v) {
    for(int i=1; i<k+1; i++) {
        if(arr[i-1] == '<') {
            if(v[i-1] > v[i]) return false;
        }
        if(arr[i-1] == '>') {
            if(v[i-1] < v[i]) return false;
        }
    }
    return true;
}


void dfs(vector<int>& v, int depth) {
    if(depth == k+1) {
        if(check(v)) {
            results.push_back(make_string(v));
        }
        return ;
    }
    for(int i=0; i<=9; i++) {
        if(!visited[i]) {
            v.push_back(i);
            visited[i] = true;
            dfs(v, depth+1);
            v.pop_back();
            visited[i] = false;
        }
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> k;
    for(int i=0; i<k; i++) {
        char tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
    vector<int> v;
    dfs(v, 0);
    if(results.size() == 1) cout << results[0] << "\n" << results[0];
    else cout << results[results.size()-1] << "\n" << results[0];
    return 0;
}