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

문제 링크:https://www.acmicpc.net/problem/18511
문제 난이도: 실버 5
문제 알고리즘: 부르트포스 알고리즘, 재귀
문제 해결 idea: K개의 원소가 주어지고, 이 원소로만 만들수 있는 경우의 수중에, N보다 작거나 같은 자연수 중 가장 큰수를 구하는 것이다. ->k개의 원소종류로 만들 수 있는 모든 수를 확인하여, 가장 큰 값을 구하도록 하자
k개의 수 만큼 원소를 벡터에 저장한다.
재귀로 주어진 k개의 수만큼 만들수 있는 모든 경우의 수를만든다.!!!!!
이 문제는 말로 풀이하는 것 보다 코드+주석을 보면 이해할 수 있을것이라 생각됩니다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

int n;
int k;
int res=0;
vector<int>v;

//num 은 주어진 k개의 종류 원소로 만들수 있는 숫자
//ten은 자릿수
void dfs(int num,int ten){
    
    if(n<num){
        return;
    }
    res=max(res,num);
    for(int i=0;i<v.size();i++){
        dfs(num+v[i]*ten,ten*10);
    }
    
    
}

int main(){
    
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
    
   
    cin>>n;
  
    cin>>k;
    
  
    
    //입력
    for(int i=0;i<k;i++){
        int input;
        cin>>input;
        v.push_back(input);
     
    }
    
    
    //정렬
    sort(v.begin(), v.end());
    
    dfs(0,1);
    
    cout<<res<<"\n";
    
    return 0;
}

더 좋은 풀이가 있거나 궁금한 점이 있다면, 편하게 댓글 남겨주세요 😊