[백준 16943번] 숫자 재배치 (C++)

문제링크 : https://www.acmicpc.net/problem/16943

16943번: 숫자 재배치

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int A, B;
string str_A;
vector<char>v;
int visited[10];
int max_V = 0, len = 0;

void dfs(string s)
{
    if(s.size() == str_A.size()) //새로 만든 문자열
    {
        int num = stoi(s);

        if(max_V < num && num < B)
        {
            max_V = num;
        }
    }
    
    for(int i=0; i<str_A.size(); i++)
    {
        if(!visited[i])
        {
            if(s.size() == 0 && str_A[i]=='0') continue; //0으로 시작 불가
            visited[i]=1;
            s.push_back(str_A[i]);
            dfs(s);
            visited[i]=0; //백트래킹
            s.pop_back();
        }
    }
}

int main()
{
    cin >> A >> B;

    str_A = to_string(A);

    dfs("");

    if(max_V == 0) cout << -1;
    else cout << max_V;
}

처음 입력받은 A만 문자열로 바꿔주고 시작한다.

A만 가지고 활용하여 백트래킹을 실시하므로 B는 문자열로 바꿔줄 필요가 없다.

 

dfs를 돌리는데, 처음에 빈 문자열을 입력받는다.

문자열 A의 값을 빈 문자열에 넣어가면서 백트래킹을 실시하고, 첫 문자가 0이면 시작이 불가능하는 것을 주의해야한다.

빈 문자열이 채워져서 A의 문자열과 길이가 같아진다면 이를 숫자로 바꿔주고 숫자 B보다 작은지를 체크해준다.

이렇게 B보다 작되, 가장 큰 숫자를 찾아서 이를 출력하면 된다.