[C++] 백준 16943번 - 숫자 재배치 (완전탐색 / DFS)

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

16943번: 숫자 재배치

 

 

문제

두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 

가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

B보다 작거나 같은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.

 

 

 

---

 

 

 

접근 방법

정수 A를 string으로 형변환 한 뒤, 각 문자를 vector에 넣고 DFS를 돌려서 완전 탐색을 해 주었다. 

DFS를 돌면서 vector안의 각 요소를 str에 push_back()으로 붙이고 pop_back()으로 빼주었다.

 

A의 자리수만큼 수를 만들었으면 정수형으로 다시 바꾼뒤 문제의 조건을 만족하는지 확인한다.

 

//
//  BF_BOJ16943_숫자재배치.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/05.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int visited[10] = {0};
vector<char> vec;
int A,B;
string strB;
int maxi = 0;
int answer = 0;
void DFS(int toPick, string str){
    
    if(toPick==0){
        int num = stoi(str);

        if(num!=A && num<B){        //B보다 작으면서
            if(maxi<num) {          //그 중 가장 큰 값
                maxi = num;
                answer = num;
            }
        }
    }
    
    for(int i = 0; i<vec.size(); i++){
        
        if(visited[i]==0){
            if(str.length()==0 && vec[i]=='0') continue;        //처음 0이 오면 안됨
            visited[i] = 1;
            str.push_back(vec[i]);
            DFS(toPick-1, str);
            str.pop_back();
            visited[i] = 0;
        }
    }
}


int main(){
    
    cin >> A >> B;
    
    string strA = to_string(A);
    string strB = to_string(B);
    int nLen = (int)strA.length();
    
    for(int i = 0; i<nLen; i++){
        vec.push_back(strA[i]);
    }
    
    DFS(nLen, "");
    if(answer==0) answer=-1;
    cout << answer ;
    
    return 0;
}