BAEKJOON 1038 - 감소하는 수

문제: https://www.acmicpc.net/problem/1038

완전탐색으로 문제를 풀 경우 시간 복잡도가 크기 때문에 다른 방법으로 접근을 해야 했습니다.

만약 n이 19일 경우

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, 40, 41, 42, 43

위와 같은 순서대로 43이 정답이 되는데, 10 이후의 숫자들을 자세히 살펴보면

앞자리가 4일 경우 올 수 있는 가짓수는 0, 1, 2, 3 사이의 숫자들 중 한 가지를 고르는 순서 없는 조합의 가짓수임을 알 수 있습니다.

즉, 이항계수로 구할 수가 있습니다.

따라서 다음과 같이 이항계수를 사용하여 시간 복잡도를 줄여 풀어볼 수 있습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
      
using namespace std;
 
typedef long long ll;
 
int BinomialCoefficient_Cache[11][11];
 
int getBinomialCoefficient(int n, int k)
{
    if (n == k || k == 0)
        return 1;
 
    if (BinomialCoefficient_Cache[n][k] != -1)
        return BinomialCoefficient_Cache[n][k];
 
    return BinomialCoefficient_Cache[n][k] = getBinomialCoefficient(n - 1, k - 1) + getBinomialCoefficient(n - 1, k);
}
 
ll makeNumber(int n, int k, int num)
{
    ll ret;
 
    if (k <= 1)
        return num - 1;
 
    int firstNumber = k - 2;
    while (true)
    {
        firstNumber++;
        int bino = getBinomialCoefficient(firstNumber, k - 1);
        if (num > bino)
            num -= bino;
        else
            break;
    }
 
    ret = firstNumber * pow(10, k - 1) + makeNumber(firstNumber - 1, k - 1, num);
    return ret;
}
 
int main()
{
    memset(BinomialCoefficient_Cache, -1, sizeof(BinomialCoefficient_Cache));
    int n;
    cin >> n;
    n++;
    ll ret = -1;
 
    for (int digit = 1; digit <= 10; digit++)
    {
        int bino = getBinomialCoefficient(10, digit);
        if (n > bino)
        {
            n -= bino;
        }
        else
        {
            ret = makeNumber(9, digit, n);
            break;
        }
    }
 
    cout << ret << endl;
    return 0;
}