Algorithm/Baekjoon

[Algorithm] Baekjoon 1038번 : 감소하는 수

MaxLevel 2023. 10. 31. 04:05

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

 

1038번: 감소하는 수

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

www.acmicpc.net

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
 
int n;
string s = "";
int standardDepth = 0;
int answerCount = -1;
 
void DFS(int depth)
{
    if (depth == standardDepth)
    {
        ++answerCount;
 
        if (answerCount == n)
        {
            cout << s;
            exit(0);
        }
 
        return;
    }
 
    int prevNum = s.back() - '0';
 
    for (int i = 0; i <= 9; ++i)
    {
        if (i >= prevNum) continue;
 
        s.push_back(i + '0');
        DFS(depth + 1);
        s.pop_back();
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 1; i <= 10; ++i) // 뎁스설정
    {
        standardDepth = i;
 
        for (int j = 0; j <= 9; ++j)
        {
            s.push_back(j + '0');
            DFS(1);
            s.pop_back();
        }
    }
 
    cout << -1;
}
 
 cs

어렵지않은 문젠데 문제이해를 이상하게 했었다...

일단 숫자자체는 감소하는 수이면서 오름차순으로 순번이 매겨지는건데, 오름차순인걸 망각하고 이상하게 순번매겼다.

 

숫자는 0~9로 총 최대숫자의개수는 10개다. 9876543210 인 경우 10개가 되기 때문에 최대 10개가 맞다.

그래서 최대숫자개수를 1개~10로 기준을 맞춰놓고 DFS를 돌렸다.

각 탐색마다 0~9를 숫자를 표현하는 string에 붙이는데, 이전숫자보다 작아야만 붙일 수 있다(감소하는 수니까).

이런식으로 완전탐색 돌리면 된다.