[ 백준 / C++ ] 1038 : 감소하는 수

[ 문제 ]

 

1038번: 감소하는 수

 

[ 접근방법 ]

 

먼저 조합 값을 미리 계산하여 combination 배열에 저장하였다.

combination[ n ][ k ] = n C k .

 

findDecreasingNumber 함수는 감소하는 수를 찾는 재귀 함수이다.

제일 앞 자리에 가능한 수를 찾고, 남은 자리수에 대해서는 재귀 호출을 통해 해결한다.

digits는 전체 자리 수, nth는 몇 번째 감소하는 수인지, maxDigit는 제일 앞자리에 가능한 제일 큰 수이다.

 

메인 로직으로는 n을 입력받으면 답이 몇 자리 수인지 확인한다.

그리고 해당 자리수에 대해 findDecreasingNumber 함수를 호출하여 정답을 구한다.

 

[ 소스코드 ]

 

#include <iostream>
#include <cmath>

using namespace std;

int n, combination[15][15];

long long findDecreasingNumber(int digits, int nth, int maxDigit){
    if(digits == 1)return nth - 1;

    int digit = 0;
    for(digit = digits - 1; digit <= maxDigit; digit++){
        if(nth <= combination[digit + 1][digits]){
            nth -= combination[digit][digits];
            break;
        }
    }

    return digit * (long long)pow(10, digits - 1) + findDecreasingNumber(digits - 1, nth, maxDigit - 1);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for(int i = 0; i <= 10; i++){
        combination[i][0] = 1;
        combination[i][i] = 1;
    }
    for(int i = 1; i <= 10; i++){
        for(int j = 1; j <= i; j++){
            combination[i][j] = combination[i - 1][j] + combination[i - 1][j - 1];
        }
    }

    int sum = -1, digits = 0;
    for(int i = 1; i <= 10; i++){
        if(n <= (sum + combination[10][i])){
            n -= sum;
            digits = i;
            break;
        }
        sum += combination[10][i];
    }

    if(digits)cout << findDecreasingNumber(digits, n, 9);
    else cout << "-1";

    return 0;
}