백준 18511 큰 수 구성하기

 

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

18511번: 큰 수 구성하기

1~9의 주어진 K개의 자연수를 이용해서, N보다 작거나 같은 수 중 가장 큰수를 구하는 문제다.

 

첫 시도는

1) N의 자릿수를 구하고

2) 자릿수 만큼 재귀적으로 K에 속한 수를 하나씩 추가한 정수를 만든 후

3) 만든 수를 모아놓는 vector에서 조건에 맞는(N보다 작거나 같은)수 중 큰 수를 구하려 했다.

틀렸다.

 

이유는 범위를 잘못 책정했다는 것이다.

1)

입력 : 

22 2

1 2

출력 :

22

문제가 없다.

 

2)

입력 :

22 2

9 9

출력 :

 

출력할 값이 없다.

자릿수가 2이므로 수의 표현은 XX일 것인데, X에 들어갈 수 있는 값은 9뿐이다.

99는 22보다 크므로 출력할 수 없다.

 

그러므로 조합할 범위는 [자릿수-1, 자릿수]가 되어야 한다.

 

#include <iostream>
using namespace std;

#include <vector>
#include <set>
#include <string>
#include <algorithm>
vector<int> ans;
void recur(int depth, int target_size, string now, const vector<int>& v){
    if(depth == target_size){
        ans.push_back(stoi(now));
    }else{
        if(depth == target_size -1)
            ans.push_back(stoi(now));
        for(int i=0; i<v.size(); i++){
            string next = now + to_string(v[i]);
            recur(depth+1, target_size, next, v);
        }
    }
}

int main(){
    int N, K; cin >> N >> K;
    vector<int> v(K);
    for(int i=0; i <K; i++) cin >> v[i];
    string tmp = to_string(N);
    int target_size = tmp.size();
    recur(0, target_size, "", v);
    sort(ans.begin(), ans.end());
    for(int i=ans.size()-1;i>=0; i--){
        if(ans[i] <= N){
            cout << ans[i];
            break;
        }
    }
    return 0;
}