백준 1038번 감소하는 수

🔒[문제 url]

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

🔑알고리즘

감소하는 수 중 최대값은 $9876543210$ 으로, 길이가 10이다.
따라서 길이가 1인 감소하는 수부터 길이가 10인 감소하는 수를 차례대로 찾고, $n$번째 감소하는 수를 찾으면 프로그램을 종료한다.

• 감소하는 수를 어떻게 찾는가?
  • 길이가 $i$인 감소하는 수를 찾는다면, 길이가 $i$가 될 때까지 문자열을 이용해 마지막 원소보다 작은 수를 뒤에 삽입해나간다.
  • 재귀를 통해 0부터 $i$까지 길이를 하나씩 늘려가며 진행하고,
    BackTracking을 통해 수를 바꾸어가며 삽입한다.

🐾부분 코드

void permutation(int cnt, int limit)
{
    if(cnt == limit)
    {
        // 감소하는 수를 하나 찾을때마다 n을 1만큼 감소시킴
        n--;
        if(n == -1)
        {// n번째 감소하는 수를 찾으면 출력 후 프로그램 종료
            cout << descendingNum;
            exit(0);
        }
        else return;
    }

    // 마지막 원소보다 작은 원소들을 삽입
    int last = (descendingNum.length()) ? descendingNum.back() - '0' : 10;
    for(int i = 0; i < last; i++)
    {
        descendingNum += i + '0';
        permutation(cnt + 1, limit);
        // BackTracking
        descendingNum.pop_back();
    }
}

<감소하는 수 찾는 함수>
재귀적으로 문자열이 계속 감소하는 수가 되게끔 삽입해나간다.
길이가 limit이 되면 감소하는 수를 하나 찾은 것이므로 n을 하나 감소시키고, -1이 되면 해당 수를 출력 후 종료한다.

void SOLVE()
{
    int len = 1;
    // 9876543210(len == 10) is Max
    while(len <= 10)
    {// 수의 길이를 하나씩 늘려감
        permutation(0, len);
        len++;
    }
    cout << -1;
}

<BruteForce 구현>
감소하는 수의 길이를 1씩 늘려가며 모든 감소하는 수를 확인한다.

<>

🪄전체 코드

#include <iostream>
#include <string>
using namespace std;

int n;
string descendingNum = "";

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
}

void permutation(int cnt, int limit)
{
    if(cnt == limit)
    {
        // 감소하는 수를 하나 찾을때마다 n을 1만큼 감소시킴
        n--;
        if(n == -1)
        {// n번째 감소하는 수를 찾으면 출력 후 프로그램 종료
            cout << descendingNum;
            exit(0);
        }
        else return;
    }

    // 마지막 원소보다 작은 원소들을 삽입
    int last = (descendingNum.length()) ? descendingNum.back() - '0' : 10;
    for(int i = 0; i < last; i++)
    {
        descendingNum += i + '0';
        permutation(cnt + 1, limit);
        // BackTracking
        descendingNum.pop_back();
    }
}

void SOLVE()
{
    int len = 1;
    // 9876543210(len == 10) is Max
    while(len <= 10)
    {// 수의 길이를 하나씩 늘려감
        permutation(0, len);
        len++;
    }
    cout << -1;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

BruteForcing + BackTracking 유형은 꽤나 뻔하다는걸 느꼈다,
며칠 몰아풀다보니 이제 손쉽게 구현하게 되었다.
물론 골딱골딱하지만..