백준 2529 부등호 (C++)

2519번: 부등호

백트래킹을 이용한 문제이다. 재귀를 통해 입력받은 부등호 조건에 만족할 경우 s에 숫자를 추가해주고 s의 크기가 k + 1과 같아질 경우 최댓값과 최솟값을 갱신해준다. 그 후 백트래킹을 통해 다음 숫자를 대입해보며 갱신을 해준 후 출력해주었다. 어렵지 않게 풀 수 있었다.

#include <iostream>

using namespace std;

int k;
char A[10];
bool check[10];
string maxr = "";
string minr = "9876543210";

void dfs(int n, string s) {
    if (s.size() == k + 1) {
        maxr = max(maxr, s);
        minr = min(minr, s);

        return;
    }

    for (int i = 0; i <= 9; i++) {
        if (check[i]) continue;
        if (A[s.size() - 1] == '>') {
            if (s.back() - '0' < i) continue;
        }
        if (A[s.size() - 1] == '<') {
            if (s.back() - '0' > i) continue;
        }

        check[i] = true;
        s.push_back(i + '0');
        dfs(i, s);
        s.pop_back();
        check[i] = false;
    }
}

void solution() {
    string s = "";

    for (int i = 0; i <= 9; i++) {
        check[i] = true;
        s.push_back((i + '0'));
        dfs(i, s);
        s.pop_back();
        check[i] = false;
    }

    cout << maxr << endl;
    cout << minr << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> k;

    for (int i = 0; i < k; i++) {
        cin >> A[i];
    }

    solution();

    return 0;
}