[백준 1038][C++] 감소하는 수 (Gold 5)

[문제보기]

1038. 감소하는 수

1038번: 감소하는 수

 

[풀이과정]

처음에는 0부터 시작해서 하나씩 증가시키면서 자릿수 별로 앞에 있는 숫자보다 작으면 감소하는 수가 아닌 수로

check 표시를 해서 감소하는 수에 대한 배열을 만들어 놓고 입력값을 받아 정답을 출력하는 코드를 만들었다. 

하지만 이렇게 할 경우 시간 복잡도가 100억이 이상이 나올 수가 있으므로 이 문제를 풀 수가 없다.

따라서, 다음 방법으로 num[11][10]( [11]은 자릿수를 뜻하고 [10]은 시작 숫자를 의미) 배열을 만든다.

예를 들어, num[2][9]라는 건 2자리 숫자가 있는데, 시작 숫자가 9라는 뜻이다. = 9X

              num[3][5] = 5XX

이렇게 배열을 통해 각 자리, 시작 숫자에 대해서 감소하는 수가 몇 개가 있는지 찾고 값들을 넣어준다. 그리고 입력값을

받아 숫자를 찾아주는데, main()에 있는 for문을 통해 처음 시작하는 수와 자리 수를 찾고 dfs()을 이용하여, 뒷자리수의 

숫자까지 찾아준다. 

[소스보기]

#include <iostream>
#include <math.h>
using namespace std;
int n;
int num[11][10] = {0};
long long ans = -1;

void dfs(int start, int digit, long long now){
    if(digit == 0){
        return;
    }

    if(digit == 1){
        now += (n-1);
        ans = now;
        return;
    }

    else{
        for(int i = 0; i<=start; i++){
            if(!num[digit][i])
                continue;

            n -= num[digit][i];
            if(n <= 0){
                n += num[digit][i];
                now += i * pow(10, digit-1);
                dfs(i-1, digit-1, now);
                break;
            }
        }
    }
}

int main(){

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

    for(int i=2; i<11; i++){
        for(int j=i-1; j<10; j++){
            if( i == j+1)
                num[i][j] = 1;
            else{
                for(int k = 0; k<j; k++){
                    num[i][j] += num[i-1][k];
                }
            }
        }
    }
    
    cin >> n;
    if(n == 0){
        cout << "0" << "\n";
        return 0;
    }
    if(n > 1022){
        cout << "-1" << "\n";
        return 0;
    }
    else if(n == 1022){
        cout << "9876543210" << "\n";
        return 0;
    }

    int start, digit;
    bool flag = false;
    for(int i=1; i<11; i++){
        for(int j=1; j<10; j++){
            if(!num[i][j])
                continue;

            n -= num[i][j];
            if(n <= 0){
                flag = true;
                ans = (long long)j * pow(10, i-1);
                n += num[i][j];
                dfs(j-1, i-1, ans);
                break;
            }
        }
        if(flag){
            break;
        }
    }


    cout << ans << "\n";
    return 0;
}

[해결과정 중 실수한 부분]

각 자릿수와 시작 숫자 테이블을 만들고 나서 단순하게 입력값이 어디 부분에 있는지만 찾고 더해주면 되겠지라고

생각을 해서 문제를 쉽게 생각을 했는데, 다시 생각해보니 뒷자리에 대한 부분도 찾아야 되기 때문에 복잡한 코드가

되었다. 문제를 너무 쉽게 생각했다...ㅠㅠ