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

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

1038번: 감소하는 수

 
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;
}
 

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

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

 

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

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

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

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