[C++] 백준 문제풀이 (Bruteforcing) 16943번 숫자 재배치

 

 

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

16943번: 숫자 재배치

 

 

 

//[C++] 백준 문제풀이 (Bruteforcing)
#include <bits/stdc++.h>


int ret = -1;
int nums[9];
bool used[9];
// k 자리수
// flag 예를들어 3자리인 경우 모든 숫자는 x >= 100을 만족해야한다.
// 그렇지 않다면 0이 백의 자리수에 온 경우에 만들어진 숫자이기 때문이다.
int A, B, flag, k;


void dfs(int depth, int sum){
    if (depth == k){
        if (sum >= flag && sum < B){
            ret = std::max(ret, sum);
        }
        return;
    }

    for (int i = 0; i < k; ++i){
        if (used[i]) continue;
        used[i] = true;
        dfs(depth + 1, sum * 10 + nums[i]);
        used[i] = false;
    }
}


int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);


    std::cin >> A >> B;

    double a = 0.1;
    while(A != 0){
        nums[k] = A % 10;
        flag = int(a *= 10);
        A /= 10;
        ++k;
    }

    dfs(0, 0);

    std::cout << ret << "\n";

    return 0;
}