[C++/백준] 2529번: 부등호

문제 링크

2529번: 부등호

 

풀이

백트래킹 문제

1. 0부터 9까지 숫자 한 번만 사용이 가능하므로 bool 배열을 통해 체크한다.
2. func함수는 숫자가 만들어질 때까지 재귀호출을 한다.
   1. num은 이전 숫자, idx는 현재 부등호, curString은 현재까지 만든 숫자, sign은 부등호의 vector, used는 사용한 숫자 체크를 위한 배열이다. used의 각 인덱스가 해당 숫자의 사용 여부이다.
   2. idx가 sign의 size와 같다면 숫자가 잘 만들어진 것이므로 minAnswer와 maxAnswer를 갱신한 뒤 return한다.
   3. 0부터 9까지 반복문을 돌며, 사용한 숫자가 아니고, 해당 숫자(i)와 이전 숫자 num과 부등호 관계가 성립한다면 재귀 호출한다.
   4. 이 때, used도 체크해준 뒤 재귀로 넘기고, 다시 돌려놓는다.
3. maxAnswer와 minAnswer를 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string minAnswer = "9876543211";
string maxAnswer = "-1";

void func(int num, int idx, string curString, vector<char>& sign, bool used[10])
{
    if (idx == sign.size())
    {
        minAnswer = min(minAnswer, curString);
        maxAnswer = max(maxAnswer, curString);
        return;
    }

    for (int i = 0; i <= 9; i++)
    {
        if (used[i]) continue; // 사용한 숫자라면
        if ((sign[idx] == '>' && num > i) || (sign[idx] == '<' && num < i))
        {
            used[i] = true;
            func(i, idx + 1, curString + to_string(i), sign, used);
            used[i] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<char> sign(n);
    for (int i = 0; i < n; i++)
    {
        cin >> sign[i];
    }

    bool used[10] = { false, };
    for (int i = 0; i <= 9; i++)
    {
        used[i] = true;
        func(i, 0, to_string(i), sign, used);
        used[i] = false;
    }

    cout << maxAnswer << '\n' << minAnswer;
}