[BOJ] 큰 수 구성하기 18511번 C++

 

문제

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의 원소로만 구성된 가장 큰 수를 출력한다.

 

접근 방식

 

K 집합에서 만들수 있는 모든 수를 재귀를 사용해 구한뒤

N보다 작으면서 가장 큰값을 구하면 된다!

 

이때 만약 N이 10이고 K의 원소들이 1,9라면

만들수 있는 가장 큰 수는 9가 된다

 

따라서 재귀 함수를 구성할 때 N과 무조건 같은 자리수를 갖는 값만 큰 수로 두지 않고

만들 수 있는 모든 수를 큰 수와 비교해야 한다!!

 

코드

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll N;
int K;
vector<int> v;
ll ans = 0;

void sol(ll cur, int len, int idx) {
    if(N >= cur && ans < cur) ans = cur;
    if(idx == len) return;
    for(int i=0; i<K; i++) {
        sol(cur*10 + v[i], len, idx+1);
    }

}

int main() {
    cin>>N>>K;
    for(int i=0; i<K; i++) {
        int x; cin>>x;
        v.push_back(x);
    }

    int len = to_string(N).length();
    for(int i=0; i<K; i++) {
        sol(v[i], len, 1);
    }
    
    cout<<ans;

}