[c++] BOJ 1038번 :: 감소하는 수

감소하는 수

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	9364	2348	1876	29.716%

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍
• 브루트 포스

---

나의 답

생각의 흐름

1. 완전 탐색 (무식하게 구현)

   처음에는 숫자를 1씩 증가시켜 하나하나 조건검사를 하면서 해당 index까지 감소하는 수를 담는 arr를 채우며 계산해나가려고 했다. 하지만 너무 오래 걸리기도 하고 감소하는 수는 9876543210 이후 나오지 않는데, 이보다 큰 수가 주어지면 계산만 오래하고 결국엔 -1 값을 반환해야함을 깨달았다.

2. 완전 탐색 (반대로 생각)

   그렇다면 반대로 생각해서 숫자를 1씩 증가시키면서 하나씩 찾는 것이 아니라 감소하는 수를 하나씩 찾아서 index에 집어넣어보자. 감소하는 수는 더 높은 자릿수의 숫자가 낮은 자릿수의 숫자보다 크기 때문에, 그 특성을 이용하면 수의 범위를 크게 줄일 수 있을 것이다. 처음 떠올린 생각이 i, j에서 모든 가능한 수를 대입해보는 방법이었다면, 이제는 j가 i보다 작은 범위 내에서 대입해보는 것이다.

   하지만 또 문제가 생겼다. 자릿수가 2자리 일 때는 i와 j만 구현하면 되지만 더 커지면 for문이 너무 중첩되고 이는 반복 계산인 거 같다.

3. 반복 계산 줄이기

   2번 계산과 똑같이 구현했으나 달라진 것은 i에서 감소하는 수를 계산할 때, j와 k의 관계까지 고려할 필요가 없는 것이다. (계산 시 for문이 2번만 필요함). 아래 코드에 구체적인 구현 방식이 나와있다.

코드

#include <iostream>
#include <cmath>

using namespace std;

long long arr[10][100000] = {};
int N;
int idx = 0;
int digit = 0;
int tmp_index[10];

long long arrN() {
    int idx = 1;
    int n = N - 9;
    while (idx <= 9&&n > tmp_index[idx]) {
        n -= tmp_index[idx++];
    }
    if (idx > 9)
        return -1;
    return arr[idx][n-1];
}

long long saveDecline() {
    do{
        digit++;
        tmp_index[digit] = 0;
        for (int i = 1; i < 10; i++) { // 1~9
            for (int j = 0; j < sizeof(arr[digit - 1])/sizeof(int); j++) { // 이전 자리수 배열 돌면서
                if (arr[digit - 1][j] / pow(10, digit-1) < i) {
                    arr[digit][tmp_index[digit]++] = i * pow(10, digit) + arr[digit - 1][j];
                    idx++;
                }
                else
                    break;
            }
        }
    } while (idx < N && digit < 9);

    return arrN();
}

int main() {
    cin >> N;
    for (int i = 0; i < 10; i++) {
        arr[digit][i] = i;
    }

    if (N<10)
        cout << arr[digit][N];
    else {
        cout<< saveDecline();
    }
}

설명

main()

우선 arr에 한 자리 수 감소하는 수를 넣는다. N이 10보다 작으면 바로 해당 값을 출력하고 10보다 크면 arr를 채우기 위해 saveDecline 함수에 들어간다.

saveDecline()

아래 그림과 같이 digit를 늘려가면서 각 digit(자릿수)마다 1~9까지 돌면서 현재 자릿수보다 한 자리 낮은 자리의 감소하는 수를 순회한다. 순회하는 수의 가장 높은 자리 수가 현재 도는 index보다 낮으면 더해서 숫자로 만든다. (3자리 감소하는 수를 만들 때, index가 2면 2자리 감소하는 수 중에 10이 가장 높은 자리 수가 1이므로 2와 합쳐질 수 있다.)

1~9까지 다 돌면 digit를 1늘려서 다음 자릿수를 계산한다. 자릿수마다 몇개의 감소하는 수가 있는지 나중 계산을 위해 저장해둔다. arr에 원소를 삽입 할 때마다 전역변수 index를 1씩 늘려 index가 N을 넘어서면 그만 계산하도록 do-while문의 조건으로 준다.

*여기서 do-while문의 조건에 digit>9가 있는 이유는 9876543210 라는 10자리 수 이후에 감소하는 수가 없기 때문이다.

이런 식으로 arr를 주어진 N개 이상으로 채우고 나면 출력할 수를 계산하는 arrN 함수에 들어간다.

arrN()

arrN 함수에서는 주어진 N에서 자릿수를 1씩 증가시키면서 어떤 자릿수의 몇 번째 칸에 (arr의 몇 행 몇 열에) 수가 저장되어있는지 계산한다. 만약 예제와 같이 18번째 수를 찾는다면 한 자리수의 갯수인 10보다는 크므로 main함수에서 통과되어 들어왔을 것이다.

따라서 N에서 9을 빼고 9이 남는다. 자릿수는 1증가하며 두 자리수 감소하는 수의 갯수를 보는데, 45개 이므로 8보다 작으니 해당 행의 N번째에 우리가 찾는 수가 있을 것이다. (arr[1][7])

*N에서 10을 빼지 않고 9을 빼는 이유는 한 자리 수의 예제로 생각해보자. 5번째 수를 찾으려면 arr의 한 자리수 행에 있는 6번째 값을 가져와야한다. 따라서 N번째 수가 0부터 시작하기 때문에 9를 빼주어야한다.

*배열의 index가 헷갈리게 되어있다. 해당 행의 N번째에 존재하므로 arr[해당 행][N-1] 을 return해야한다.

결과

arr는 다음과 같이 채워진다. 마지막 10자리 수 감소하는 수는 9876543210 하나이고 그 이후는 존재하지 않는다. 그리고 구현해본 결과 1022번째 수가 9876543210이고 1023부터는 -1이 나와야한다.

---

다른 답

https://blog.encrypted.gg/142

BaaaaaakingDog 님의 풀이는 먼저 집합의 특성을 이용해서 감소하는 수의 갯수가 최대 1023개밖에 없음을 알아내고, 1023개의 수를 구한 후 정렬하는 방식이다.

=> 비트 마스크를 이용하였다. (너무 대단하심.. 흑흑)

https://postbarca.tistory.com/46

큐를 이용해서 간단하게 구현하였다. 멋있다.