(C++) - 백준(BOJ) 1174 : 줄어드는 수

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

1174번: 줄어드는 수

전수조사 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

수 n, check를 위한 배열 ck, 수 목록 num, 정답을 출력할 ans, 뽑은 수들을 저장할 comb를 선언한 후 적절히 입력 받습니다.

📔 풀이과정

줄어드는 수의 최대값은 9876543210입니다. 이는 자릿수마다 배열 num에 저장해 둡니다.줄어드는 수를 결정하는 가짓수는 다음처럼 생각해볼 수 있습니다. 각 자리를 선택하거나 선택하지 않거나로 두 가지 경우로 나뉘므로 2^10가지 경우로 나뉘게 됩니다. 순서가 상관 있기 때문에 조합으로 dfs함수를 수행해 이전 index 자리 수를 뽑지 않도록 해 comb에 저장합니다.

📔 정답출력

index가 0부터 시작하므로 n이 1024인 경우부터 -1을 출력합니다.

이외에는 ans[n-1]을 출력합니다.

---

📕 Code

조합으로 구현

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

int n, ck[10];
ll num[] = {9,8,7,6,5,4,3,2,1,0};
vector <ll> ans, comb;

void dfs(int depth, int idx, int piv){
    if(depth == piv){
        ll sum = 0;
        for(auto c : comb){
            sum += c;
            sum *= 10;
        }
        sum /= 10;
        ans.push_back(sum);
        return;
    }
    for(int i = idx; i < 10; i++){
        if(ck[i]) continue;
        ck[i] = 1;
        comb.push_back(num[i]);
        dfs(depth+1, i+1, piv);
        comb.pop_back();
        ck[i] = 0;
    }
}

int main(){
    cin >> n;
    if(n > 1023) { cout << -1; return 0; }
    for(int i = 1; i <= 10; i++)
        dfs(0,0,i);
    sort(ans.begin(), ans.end());
    cout << ans[n-1];
}

 

 

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.