[ 백준 2529 ] 부등호 (C++)

백준의 부등호(2529) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 어려워 보이지만, 구해야하는 것을 알고나면 훨씬 쉬워진다.

   우리가 구해야 할 것은 0~9까지 나올 수 있는 모든 숫자들의 순열을 구하면 되는 것이다.

   순열을 구현하는 방법을 잘 모른다면 아래의 링크를 타고 순열을 구하는 법을 알아오자 !

 

  [ 순열 구현방법 알아보기(Click) ]

   이 문제에서는 0 ~ 9까지 총 10개의 숫자중에서, 문제의 입력에 따라 알맞게 원하는 갯수만큼 뽑아서 만들 수 있는

   모든 순열을 만들어보면 된다.

   모든 순열을 만들어 본 후에, 문제에서 제시하는 조건에 그 순열이 부합하는지 판단 후, 맞다면 답을 도출하면 되는

   것이다.

 

   순열만 구할줄 안다면 어렵지 않은 문제이다 !

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
int K;
int Arr[MAX];
char MAP[MAX];
bool Select[MAX];
 
vector<string> Answer;
vector<char> V;
 
void Input()
{
    cin >> K;
    for (int i = 0; i < K; i++)
    {
        char a; cin >> a;
        MAP[i] = a;
    }
 
    for (int i = 0; i < 10; i++)
    {
        Arr[i] = i;
    }
}
 
bool Check(int Idx, char c)
{
    if (c == '<')
    {
        if (V[Idx] - '0' < V[Idx + 1] - '0') return true;
        else return false;
    }
    else if (c == '>')
    {
        if (V[Idx] - '0' > V[Idx + 1] - '0') return true;
        else return false;
    }
}
 
bool Calculate()
{
    for (int i = 0; i < K; i++)
    {
        if (Check(i, MAP[i]) == false) return false;
    }
    return true;
}
 
void DFS(int Cnt)
{
    if (Cnt == K + 1)
    {
        if (Calculate() == true)
        {
            string S_Tmp = "";
            for (int i = 0; i < V.size(); i++)
            {
                S_Tmp = S_Tmp + V[i];
            }
            Answer.push_back(S_Tmp);
        }
        return;
    }
 
    for (int i = 0; i < 10; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(Arr[i] + '0');
        DFS(Cnt + 1);
        V.pop_back();
        Select[i] = false;
    }
}
 
void Solution()
{
    DFS(0);
    sort(Answer.begin(), Answer.end());
    cout << Answer.at(Answer.size() - 1) << endl;
    cout << Answer.at(0) << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}