[백준] 1038. 감소하는 수 (C)

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

문제

음이 아닌 정수 X의 자릿수가 큰 자릿수부터 작은 자릿수까지 감소하면 그 수는 감소하는 수

EX : 321, 950은 감소하는 수

EX : 322, 958은 감소하지 않음

N번째 감소하는 수를 출력하는 프로그램을 작성

0은 0번째 감소하는 수, 1은 1번째 감소하는 수

만약 N번째 감소하는 수가 없다면 -1을 출력

N의 범위 : 0 ~ 1,000,000

예제 입력 1

18

예제 출력 1

42

예제 입력 2

0

예제 출력 2

0

예제 입력 3

500000

예제 출력 3

-1

 

---

아이디어

점화식을 세운다?

unsigned long long -> 0부터 18,446,744,073,709,551,615 (8byte)

d[0] = 0 ->

d[1] = 1 -> 1

d[2] = 2 -> 1, 2

...

d[9] = 9 -> 1, 2, ... , 9

d[10] = 10 -> 1, 2, ... , 9, 10

d[11] = 20 -> 1, 2, ... , 9, 10, 20

d[12] = 21 -> 1, 2, ... , 9, 10, 20, 21

d[13] = 30 -> 1, 2, ... , 9, 10, 20, 21, 30

30, 31, 32

40, 41, 42, 43

50, ... , 54

...

100

200 210

300 310 320 321

400 410 420 421 430 431 432

500 510 520 521 530 531 532 540 541 542 543

...

900 910 920 921 930 931 932 ... 980 981 982 983 ... 987

1000

2000 2100

3000 3100 3200 3210

4000 4100 4200 4210 4300 4310 4320 4321

5000 5100 5200 5210 5300 5310 5320 5321 5400 5410 5420 5430 5431 5432

1의 자리 -> 9

10의 자리 -> 1+2+3+4+...+9

100의 자리 -> (1) + (1+1) + (1+1+2) + (1+1+2+3) + (1+1+2+3+4) + ... + (1+1+2+3+4+5+6+7+8+9)

1000의 자리 -> ?

1억의 자리 -> ?

이거의 문제는 숫자를 입력 받았을 때 넣어둘 수 없음, 패턴 찾기도 어렵고 최대 숫자 구하기임

그렇다면 d[500000] 으로 미리 공간을 받아놓는다면? -> 내가 볼 땐 이게 힌트임

unsigned long long으로 저장하고, 특정 함수를 만들어서 자릿수에 계속 저장하기

1에서부터 10,000,000,000,000,000,000까지 1씩 더한 수를 추가하며 계산? 그러면 근데 문제는 시간제한 1초에 걸리는데..

---

문제를 풀다가 다시 생각하게 된 것

100은 감소하는 수가 아님!

그래서, 최대 감소하는 수는 9876543210

210

310 320 321

410 420 421 430 431 432

510 520 521 530 531 532 540 541 542 543

...

910 920 921 930 931 932 ... 980 981 982 983 ... 987

3210

4210 4310 4320 4321

5210 5310 5320 5321 5410 5420 5430 5431 5432

...

43210

53210 54210 54310 54320 54321

1의 자리 -> 9

10의 자리 -> 1+2+3+4+...+9 = 45

100의 자리 -> (1) + (1+2) + (1+2+3) + (1+2+3+4) + ... + (1+2+3+4+5+6+7+8) =

1000의 자리 -> (1) + (1+3) + (1+3+5) + ... + (1+3+5+7+9+11+13)

10000의 자리 -> (1) + (1+4) + ... + (1+4+7+10+13+16)

10만의 자리 -> (1) + (1+5) + ... + (1+5+9+13+17)

100만의 자리 -> 1 + (1+6) + ... + (1+6+11+16)

1000만의 자리 -> 1 + (1+7)

1억의 자리 -> 1

대강 예측해보면 2000 보단 작을 것

숫자는

1 -> 1보다 작은 숫자 조합해서 만들어서 넣기, [10]

2 -> 2보다 작은 숫자 조합해서 만들어서 넣기, [21, 20]

 

#include <stdio.h>
#include <stdlib.h>

#define MAX_COUNT 1024  // 감소하는 수의 최대 개수 (여유롭게 설정)

long long decreasing_numbers[MAX_COUNT];  // 감소하는 수를 저장할 배열
int count = 0;  // 감소하는 수의 개수

// 감소하는 수를 재귀적으로 생성하는 함수
void generate_decreasing(long long num, int last_digit) {
    decreasing_numbers[count++] = num;  // 현재 숫자를 배열에 저장

    for (int i = 0; i < last_digit; i++) {  // 마지막 자리보다 작은 숫자만 붙이기
        generate_decreasing(num * 10 + i, i);
    }
}

// 감소하는 수를 생성하는 함수
void create_decreasing_numbers() {
    for (int i = 0; i <= 9; i++) {  // 0부터 9까지 시작하는 감소하는 수 생성
        generate_decreasing(i, i);
    }
}

// 숫자 정렬을 위한 비교 함수 (qsort에 사용)
int compare(const void *a, const void *b) {
    long long num1 = *(long long *)a;
    long long num2 = *(long long *)b;
    return (num1 > num2) - (num1 < num2);
}

int main() {
    int N;
    scanf("%d", &N);

    create_decreasing_numbers();  // 감소하는 수를 생성
    qsort(decreasing_numbers, count, sizeof(long long), compare);  // 정렬

    if (N >= count) printf("-1\n");  // N번째 감소하는 수가 없으면 -1 출력
    else printf("%lld\n", decreasing_numbers[N]);  // N번째 감소하는 수 출력

    return 0;
}​

---

최종 흐름

1. 0에서부터 숫자 시작
2. 1이 오면 다음과 같이 흐름 진행
   1. 1 저장, 다음 숫자 생성
   2. 10 저장, 종료
3. 2가 오면 다음과 같이 흐름 진행
   1. 2 저장, 다음 숫자 생성
   2. 20 저장, 종료
   3. 21 저장, 다음 숫자 생성
   4. 210 저장, 종료
4. 이후도 동일한 흐름으로 반복

이렇게 저장 한 뒤, compare를 통해 오름차순으로 숫자를 저장하여 정렬해준다.

---

후기

우선 해보면서 느낀 건, 쉬운 방식으로 풀이가 가능하지만 이걸 생각해서 만들어내는 능력이 나에게 부족하다.

숫자를 만드는 것은 분명 쉬운데, 이 방식을 제대로 생각해내기까지 너무 오래걸렸다.

사고 능력이 부족하다고 느껴진 문제였고, 다양한 문제를 풀면서 문제 해결 능력을 충분히 더 키워야 할 것 같다.

그리고 C언어로 qsort와 같은 것을 사용하는 방법은 인터넷의 도움을 받았기에, 이 관련 내용을 정리해보고자 한다.