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

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

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> num;
int a, b;
int ans = -1;

bool visit[12];

void dfs(int k, int cnt) {

    if (k == 0 && cnt == 0) {
        return;
    }

    if (cnt == num.size()-1) {
        if (k < b) {
            ans = max(ans, k);
        }
        return;
    }

    for (int i = 0; i < num.size(); i++) {
        if (!visit[i]) {
            visit[i] = true;
            dfs(k * 10 + num[i], cnt + 1);
            visit[i] = false;
        }
    }


}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> a >> b;



    while (a > 0) {
        num.push_back(a % 10);
        a /= 10;
    }


    for (int i = 0; i < num.size(); i++) {
        visit[i] = true;
        dfs(num[i], 0);
        visit[i] = false;
    }

    cout << ans;

    return 0;
}

1. 문제

두 자연수 a, b가 주어진다. a를 재배치하여 새로 만든 수 중 b보다 작으면서 가장 큰 수를 구하라.

2. 풀이

a를 한 자리씩 뜯어서, 백트래킹을 이용하여 숫자를 새로 만들어 풀 수 있다.

    while (a > 0) {
        num.push_back(a % 10);
        a /= 10;
    }

우선 a를 한 자리씩 뜯어 벡터에 저장한다.

    for (int i = 0; i < num.size(); i++) {
        visit[i] = true;
        dfs(num[i], 0);
        visit[i] = false;
    }

그리고 각 자리 수에 대해 dfs를 돌린다.

void dfs(int k, int cnt) {

    if (k == 0 && cnt == 0) {
        return;
    }

    if (cnt == num.size()-1) {
        if (k < b) {
            ans = max(ans, k);
        }
        return;
    }

    for (int i = 0; i < num.size(); i++) {
        if (!visit[i]) {
            visit[i] = true;
            dfs(k * 10 + num[i], cnt + 1);
            visit[i] = false;
        }
    }


}

가장 첫 자리는 0이 올 수 없으므로 계산하지 않는다. 각 자리를 돌면서 아직 사용하지 않은 숫자라면 뒤에 붙여 새 숫자를 만든다. a 자릿수만큼 수를 만들었다면 b보다 작은 지 확인하고, 작다면 ans의 최댓값을 갱신한다. 연산이 끝나고 ans를 출력하면 정답을 구할 수 있다.