[백준] 1038 - 감소하는 수

1. 문제

1038번: 감소하는 수

2. 개요

음이 아닌 정수 X에서 가장 큰 자릿수의 숫자부터 가장 작은 자릿수의 숫자까지 계속해서 숫자가 작아진다면 이를 감소하는 수라고 한다.

이 때 N번째 감소하는 수를 구하는 문제. N번 째 수가 존재하지 않는다면 -1을 출력한다.

3. 풀이 및 코드

3-1. 풀이

감소하는 수는 어떤 감소하는 수의 마지막 자리 보다 작은 수를 붙여서 새로 만들 수 있다.

93 이 있다면 3보다 작은 모든 숫자를 이어붙인 932, 931, 930등이 만들어질 수 있다.

이를 이용하여 백트래킹 함수를 만든다.

감소하는 수의 최대값은 9876543210인 10자리이므로 이보다 크다면 리턴한다.

백트래킹 함수를 이용해 만들어진 수를 리스트에 넣고, 정렬하여 N번째 감소하는 수를 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())
nums = []

def BT(num, length):
    if length > 10:
        return

    nums.append(num)
    
    for i in range(num % 10):
        BT(num * 10 + i, length + 1)

if N < 10:
    print(N)

elif N > 1022:
    print(-1)

else:
    for i in range(10):
        BT(i, 1)

    nums.sort()
    print(nums[N])

3-3. C#

namespace boj_1038
{
    internal class Program
    {
        static List<long> nums  = new List<long>();

        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            if (N < 10)
                Console.WriteLine(N);

            else if (N > 1022)
                Console.WriteLine(-1);

            else
            {
                for (int i = 0; i < 10; i++)
                {
                    BT(i, 1);
                }

                nums.Sort();
                Console.WriteLine(nums[N]);
            }
        }

        static void BT(long num, int length)
        {
            if (length > 10)
                return;

            nums.Add(num);

            for (int i = 0; i < num % 10; i++)
            {
                BT(num * 10 + i, length + 1);
            }
        }
    }
}