문제 링크: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;
}
더 좋은 풀이가 있거나 궁금한 점이 있다면, 편하게 댓글 남겨주세요 😊