[재귀] BOJ 2529 부등호

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

2529번: 부등호

- 문제 파악

부등호 문자열을 주고 부등호 사이에 각 부등호를 만족하는 수를 넣는다. 그 수를 합쳐서 한 개의 수를 만들 때 그 수의 최대값과 최소값을 출력하라.

 

- 정답

재귀 함수 완전탐색

#include "bits/stdc++.h"

using namespace std;


int n;

char szarr[10];
int narr[10];

string strmax;
string strmin;

string strtmp;

unsigned long long  nmax = 0;
unsigned long long  nmin = 0x7ffffffff;


/*
* k n
* 0 -1
* 1 0
* 2 1
*/

void func(int k)
{
    if (k == n+1)
    {
        unsigned long long ntmp;

        ntmp = stoull(strtmp);

        nmax = max(nmax, ntmp);
        nmin = min(nmin, ntmp);

        strmax = to_string(nmax);
        strmin = to_string(nmin);

        if (strmax.length() != k)
            strmax = "0" + strmax;

        if (strmin.length() != k)
            strmin = "0" + strmin;


        return;
    }

    for (int i = 0; i < 10; i++) // 0~9까지만 존재
    {
        if (k != 0)
        {
            int ntmp = strtmp[k - 1] - 0x30;

            if (szarr[k-1] == '<')
            {
                if (i <= ntmp) // ntmp >= i 면 continuie
                    continue;

                if (!narr[i])
                {
                    strtmp[k] = (i + 0x30);
                    narr[i] = 1;
                    func(k + 1);
                    narr[i] = 0;
                }
            }
            else if (szarr[k-1] == '>')
            {
                if (i >= ntmp)
                    continue;

                if (!narr[i])
                {
                    strtmp[k] = (i + 0x30);
                    narr[i] = 1;
                    func(k + 1);
                    narr[i] = 0;
                }
            }
        }
        else
        {
            strtmp[k] = (i + 0x30);

            narr[i] = 1;
            func(k + 1);
            narr[i] = 0;

        }

    }

}


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

    cin >> n;

    strmax.resize(n +1);
    strmin.resize(n +1);
    strtmp.resize(n +1);

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

    func(0);

    cout << strmax << "\n";
    cout << strmin << "\n";



}