반응형

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

 

1038번: 감소하는 수

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 감소하는 수의 최댓값은 9876543210이므로 감소하는 수의 자릿수의 최댓값은 10입니다.

 

2. 최대 자릿수를 1부터 10까지 for문을 돌면서 숫자들을 탐색하고, 감소하는 수가 나올 때마다 cnt++를 해주고, cnt == N이 될 때 해당 수를 출력해 줍니다.

 

3. 감소하는 수의 최대 개수는 1022개 이므로 N이 1023 이상이라면 -1을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int bucket[10];
int cnt = -1;
 
void dfs(int level, int limit)
{
    if (cnt >= N) return;
    if (level == 0) {
        cnt++;
        if (cnt == N) {
            for (int i = limit - 1; i >= 0; i--) {
                cout << bucket[i];
            }
        }
        return;
    }
 
    for (int i = level - 1; i < 10; i++) {
        if (level != limit) {
            if (bucket[level] > i) {
                bucket[level - 1] = i;
                dfs(level - 1, limit);
                bucket[level - 1] = 0;
            }
            else {
                return;
            }
        }
        else {
            bucket[level - 1] = i;
            dfs(level - 1, limit);
            bucket[level - 1] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    if (N > 1022) cout << -1;
 
    for (int i = 1; i <= 10; i++) {
        dfs(i, i);
        if (cnt >= N) break;
    }
 
    int de = -1;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 6198번 - 옥상 정원 꾸미기 (C++)  (0) 2023.07.07
[ 백준 ] 1456번 - 거의 소수 (C++)  (0) 2023.07.06
[ 백준 ] 11402번 - 이항 계수 4 (C++)  (0) 2023.07.04
[ 백준 ] 11401번 - 이항 계수 3 (C++)  (0) 2023.07.02
[ 백준 ] 17025번 - Icy Perimeter (C++)  (0) 2023.07.01

+ Recent posts

티스토리툴바