Easy is Perfect

[백준] 1038번 C/C++ 풀이 _ 감소하는 수

  • melonicedlatte
  • Feb 23, 2018


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

감소하는 수 성공 풀이

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB353489372629.560%

문제

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

입력

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

출력

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

예제 입력 

18

예제 출력 

42

힌트

출처

알고리즘 분류

>> 문제 풀이 방법

처음에 문제를 읽어 보고 우습게 보다가 설계를 잘 못 해서 시간이 매우 오래 걸렸다. 
문제는 읽었을 때 쉬워보였는데, 시간 복잡도 계산을 제대로 하지 않아서 잘못된 설계였다.
(문제 부류가 블루탈 포스라서 너무 쉽게 생각하고 풀었던 것 같다.)
어쩐지 정답률이 30% 보다 낮더라니

처음에는 아래처럼 1부터 시작해서 숫자를 하나씩 증가시켜 가면서, 확인했다. 
자리수별로 앞에 있는 숫자보다 작으면 옳지 않은 숫자라고 판단하고 종료하는 방식이다. 


시간 복잡도를 분석해보면, n 자리수를 분석하기 위해서는 약 밑의 그림에서 Sn 과 같은 복잡도를 가지게 된다.
이 문제에서 최대로 나올 수 있는 숫자를 생각해보면 9876543210 과 같은 10자리 숫자이다. 
10을 넣어보고 전체 합산이 아니라 10자리 숫자만 계산해야하는 횟수를 계산해보면 4.5 x 1010  정도가 나오게 되어 계산량이
너무 많다는 것을 확인할 수 있다. ( 약, 1010 =100억  )


그래서 새로운 구조로 생각을 해 보게 되었다.
계속 보다보니 규칙성 같은게 눈에 띄었다. 

k로 시작한 1자리 숫자는 10개이고 전부 1개씩의 감소하는 숫자가 존재하고, 
k로 시작한 2자리 숫자는 9개이고 1, 2, 3, 4, 5, 6 ,7 ,8, 9 만큼의 가능한 숫자가 있다. 
k로 시작한 3자리 숫자는 8개이고 1, 3, 6, 10, .... 만큼이 가능하다. 

이를 표현해보면 아래와 같이 나타낼 수 있다.
어떤 좌표에 있는 값(i, j )을 구하기 위해서는 한 칸 row 아래 (i-1)에서 (0~j-1) 까지의 수를 모두 더하여 구한다. 

 


위의 숫자를 구하는 것은 10x10 행렬이기 때문에 매우 빠른 속도로 진행 될 것이다.
구하고자하는 n 번째에 있는 숫자를 위에있는 숫자를 row 의 순서대로 순차적으로 더하면서 
원하는 순차에 있는 숫자보다 크거나 같을 때 까지의 좌표를 구한다. 
좌표를 구하면 자리수와 시작숫자를 알 수 있다. 

자리수와 시작숫자를 알고 나서 바로 dfs를 이용하여 값을 구한다. 
자리수와 시작숫자를 알게 되면 dfs에 적용될 수 있는 숫자는 크지 않다. 

4자리 숫자에서 시작숫자가 7 이라고 가정해보자. 
그 다음에 올 수 있는 숫자는 6~0 이 있다. 
하지만 0과 1이 오면 그 다음에 올 수 있는 숫자가 남은 칸수인 2보다 작기 때문에 6~2 사이의 숫자만 가능하다. 


그리고 다음 단계로 넘어가서 74()()를 살펴보면 3~0 사이의 숫자에서,
남은 자리 수가 1자리이기 때문에 0 을 제외한 숫자가 다 들어갈 수 있다. 


따라서, dfs 를 적용할 때에는 확정된 숫자 중에서 가장 작은 자리 숫자보다 작은 숫자들 중에서
남은 자리 수만큼의 숫자를 빼고 dfs 에 넣으면 된다. 

식은 아래와 같이 구성되는데, 감소하는 숫자는 dfs의 각 단계에서 위에서 구한 10*10 배열의 원소 값과 같다. 
최대 약 140 정도이다. 



따라서, 전체 시간 복잡도는 매우 작다고 볼 수 있다. 

>> 소스코드 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <math.h>
 
using namespace std;
 
int find_decrease_num, sum = 0;
int isGetAnswer = 0, isEndCheck = 0;
int num_arr[10][10] = { 0 };
long long answer = 0;  
 
// 배열 생성 
void make_arr() {
    // 첫 라인 개수 생성 
    for (int j = 0; j < 10; j++)   num_arr[0][j] = 1;
 
    // 나머지 배열 채우기 
    for (int i = 1; i < 10; i++) {
        for (int j = i; j < 10; j++) {
            if (j == i)  num_arr[i][j] = 1;
            else
                for (int k = i - 1; k < j; k++) num_arr[i][j] += num_arr[i - 1][k];
        }
    }
}
 
int dfs(long long start_num, long long digit, long long now_num) {
    if (isGetAnswer) return 0; 
    // 자리수가 마지막 1의 자리 수이면 sum 추가 (처음 들어오는 숫자는 제외)
    if (digit == 1) { 
        if (!isEndCheck) isEndCheck = 1;
        else    sum++;
    }
    else {
        // 다음 자리수들로 윗 자리수보다 작고 아래 자릿 수로 가능한 숫자를 dfs 로 구하기
        for (long long i = digit-2 ; i < start_num; i++)
            dfs( i, digit-1, now_num+ (long long)(i * pow(10, digit - 2)) );
    }
    // 답을 구하면 flag 를 수정한다. 
    if ((sum == find_decrease_num) && !isGetAnswer) {
        answer = now_num;
        isGetAnswer = 1;
    }
}
 
int main() {
    make_arr();
 
    cin >> find_decrease_num;
    if (find_decrease_num == 0) {
        cout << 0;
        return 0;
    }
 
    long long start_num;
    long long digit;
    int isFindRange = 0; 
 
    // 숫자의 범위를 찾아낸다. 
    for (int i = 0; i < 10 && (!isFindRange) ; i++) {
        for (int j = i; j < 10 && (!isFindRange); j++) {
            if ( (sum + num_arr[i][j]) > find_decrease_num){
                isFindRange = 1;
            }
            else {
                digit = i + 1;
                start_num = j+1;
                sum += num_arr[i][j];
            }
        }
    }
 
    // 시작 숫자 생성 
    long long now_num = (long long)(start_num * pow(10, digit - 1));
    if (find_decrease_num == 1022) {
        now_num = 9876543210;
    }
 
    // 바로 찾으면 바로 출력 
    if (sum == find_decrease_num) {
        if (sum == 1023)  answer = -1;
        else answer = now_num;
    }
    else if (find_decrease_num > 1022  ) {
        answer = -1;
    }
    // 아니면 dfs 탐색 
    else dfs(start_num, digit, now_num);
 
    cout << answer; 
 
    return 0; 
}
cs



Search