2529번 부등호

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

백트래킹 문제이다.

근데 왜 문제 분류는 위상정렬(그래프)인지는 모르겠다.

첫 시작(=before이 -1)은 무조건 실행돼야 하므로,

13번 째 줄에 if조건문을 추가했다.

백트래킹 함수(bt)의 idx는 vc(부등호) 벡터의 인덱스이다.

#include <bits/stdc++.h>
 
using namespace std;
 
int K;
string s, mins = "", maxs = "";
vector<char> vc;
bool use[10];
bool calc;
 
bool chk(int before, int now, char oper)
{
    if (before == -1) return true;
    if (oper == '>') return before > now;
    return before < now;
}
 
void bt(int idx, int before, string numbers)
{
    if (idx == K)
    {        
        if(!calc)mins = numbers;
        else maxs = max(maxs, numbers);
        calc = true;
        return;
    }
 
    for (int i = 0; i <= 9; i++)
        if (!use[i] && chk(before, i, vc[idx]))
        {
            use[i] = true;
            numbers += to_string(i);
 
            if(before == -1) bt(idx, i, numbers);
            else bt(idx + 1, i, numbers);
 
            use[i] = false;
            numbers = numbers.substr(0, numbers.length() - 1);
        }    
}
 
int main(void)
{
    cin.tie(0);
    cin >> K;
    getchar();
    getline(cin, s);
    for (auto i : s) if (i != ' ') vc.push_back(i);
    bt(0, -1, "");
 
    cout << maxs << '\n' << mins << '\n';
 
    return 0;
}