[백준/c++] 18511번: 큰 수 구성하기

 

 

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

18511번: 큰 수 구성하기

 

시행착오

처음엔 BackTracking으로 k 자리 수를 구성하면 되는 줄 알았다. 그런데 반례들을 생각하면 틀리게 되는데,,,

 

반례 1)

12 2
2 5

이 경우, 22 25 52 55 중 아무것도 12보다 작거나 같지 않기 때문에 0을 출력한다. 그러나 정답은 5가 나와야 한다.

이 예제를 통해 집합 K의 원소로만 구성된 가장 큰 수란, 집합 속의 원소를 모두 사용하지 않아도 된다는 것이다.

즉, 2 5 22 25 52 55 (1의 자리부터 k 자리까지 모두 체크해봐야 한다)

 

반례 2)

3333 3
1 2 3

이 경우, 333으로 출력되지만 정답은 3333이다. 즉, 이 반례를 통해서 집합 K의 원소를 모두 사용하는 것은 맞지만 꼭 K 자릿수가 나와야 하는 것은 아니라는 것을 알 수 있다. 

 

 

---

 

 

재귀 함수를 빠져나오기 위해서 종료 조건이 필요하다. n과 같은 자릿수를 result가 가지게 되면 빠져나오도록 한다.

n과 같은 자릿수를 가지고 있고 K의 모든 원소를 구성하는 모든 경우의 수를 확인하면 끝이 난다.

 

이 반례들을 토대로 기존에 작성했던 BackTracking 함수를 수정해야 한다. 전에는 구성한 수의 자릿수가 k개면 ans를 업데이트하고 나왔지만 이번엔 구성한 수(result)의 자릿수가 1개 이상이고, n보다 작거나 같은 값이라면 ans를 업데이트한다.

 

 

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

string n, result;
int k, ans = 0;
vector<int> v;

void BackTracking(){
    if(result.length()>0 && stoi(n) >= stoi(result)){
        ans = max(ans, stoi(result));
    }
    if(result.length() == n.length()){
        return;
    }
    
    for(int i=0; i<v.size(); i++){
        result += to_string(v[i]);
        BackTracking();
        result.pop_back();
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    v.resize(k);
    for(int i=0; i<k; i++) cin >> v[i];
    BackTracking();
    cout << ans << '\n';
    return 0;
}