(C++) - 백준(BOJ) 18511 : 큰 수 구성하기

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

18511번: 큰 수 구성하기

모든 경우의 수를 탐색하는 brute force문제였습니다.

📕 풀이방법

📔 입력 및 초기화

n, k, 정답을 출력할 ans, k집합 vector setK, 순열을 뽑을 vector permutation를 선언하고 입력받습니다.

📔 풀이과정

2가지를 구현해야 합니다.

1. k개의 원소중 x개를 뽑아 순열로 만듭니다.

2. 뽑은 원소로 수를 이어 붙인 뒤 n과 비교해 유효하면 ans에 최댓값을 저장합니다.

 

1.을 수행하기 위해 dfs함수를 수행합니다. 구한 정답이 n보다 자리수가 적을 수 있으므로 1부터 n의 자리수까지 dfs함수를 수행해 x개를 뽑아 모두 비교해야합니다.

📔 정답출력

ans를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, k, ans;
vector <int> setK, permutation;

void dfs(int depth, int length){
  if(depth == length) {
    int madeNum = 0;
    for(auto p : permutation) {
      madeNum += p;
      madeNum *= 10;
    }
    madeNum /= 10;
    if(n >= madeNum) ans = max(ans, madeNum);
    return;
  }
  for(int i = 0; i < k; i++){
    permutation.push_back(setK[i]);
    dfs(depth+1, length);
    permutation.pop_back();
  }
}

int main(){
  cin >> n >> k;
  setK.resize(k);
  for(int i = 0; i < k; i++) cin >> setK[i];
  for(int i = 1; i <= to_string(n).size(); i++) dfs(0, i);
  cout << ans;
}

---

📕 Test Case

몇 가지 반례를 작성했습니다.

input
11 1
1
답 : 11

 

input
10 1
1
답 : 1

 

input
15 2
9 9
답 : 9