백준 18511 C++ 큰 수 구성하기

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

18511번: 큰 수 구성하기

---

문제

N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 프로그램을 작성하시오. K의 모든 원소는 1부터 9까지의 자연수로만 구성된다.

예를 들어 N=657이고, K={1, 5, 7}일 때 답은 577이다.

---

입력

첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다.

단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.

---

출력

첫째 줄에 N보다 작거나 같은 자연수 중에서, K의 원소로만 구성된 가장 큰 수를 출력한다.

---

N과 K가 주어지고, K의 원소로 구성된 자연수 중에 N보다 작거나 같은 자연수이면서 K의 원소로 만들 수 있는 가장 큰 수를 출력하는 문제입니다.!

 

재귀로 해결하였으며, 먼저 정수를 입력받아 문자 벡터에 모두 넣어줍니다.

string input; //문자열
    cin >> input;
  
    n = input.size(); //문자열 길이
    N = stoi(input); //자연수
    
    cin >> k;

    for(int i = 0;i<k;i++){ //자연수 -> 문자 벡터에 넣기
        char c;
        cin >> c;
        v.push_back(c);
    }

 

그 후 DFS를 0부터 돌리기 시작하는데 DFS를 호출 할때마다 새로운 문자열을 만들고,

새로운 문자열은 문자 벡터에 있는 문자를 더한 문자열이 됩니다. 

이 문자열을 정수로 바꿔서 앞의 N보다 작거나 같으면 최대값을 이 정수로 갱신해줍니다.

 string new_str = "";
     for(int i = 0;i<start;i++){
            new_str += combinate[i];
        }
    if(new_str.size() >= 1){
        int temp = stoi(new_str);
        if(temp >= max_value && temp <= N){
            max_value = temp;
        }
    }

 

문자열의 길이만큼 DFS가 올 떄가 기저조건이고, 이 경우에도 앞에서 했던 것처럼

최대값을 갱신해줍니다.

 

전체 소스 코드->

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

int N;
int n;
int max_value = -1;
int k;
vector<char> v;
vector<char> combinate;

void dfs(int start){
     string new_str = ""; //새 문자열
     for(int i = 0;i<start;i++){ //문자 벡터를 모두 더해주고
            new_str += combinate[i];
        }
    if(new_str.size() >= 1){ //문자열 -> 정수로 바꾸고 최대값 갱신
        int temp = stoi(new_str);
        if(temp >= max_value && temp <= N){
            max_value = temp;
        }
    }
    if(start == n){ 
        int temp = stoi(new_str);
        for(int i = 0;i<start;i++){
            new_str += combinate[i];
        }
        if(temp >= max_value && temp <= N){
            max_value = temp;
        }
        return;
    }
    
    for(int i = 0;i<k;i++){ //완전탐색
        combinate.push_back(v[i]);
        dfs(start+1);
        combinate.pop_back();
    }
}
int main(void){
    string input; //문자열
    cin >> input;
  
    n = input.size(); //문자열 길이
    N = stoi(input); //자연수
    
    cin >> k;

    for(int i = 0;i<k;i++){ //자연수 -> 문자 벡터에 넣기
        char c;
        cin >> c;
        v.push_back(c);
    }

    dfs(0);
    
    cout << max_value;
}