[C++] 백준 7696 : 반복하지 않는 수

#include <iostream>
#include <string>
# define MAX 8

using namespace std;

int cnt = 0; // 몇번째 수열(수) 인지 기록할 변수
int arr[10]; //수열을 기록할
int answer [1000001][10]; //재귀로 구한 데이터를 넣을 곳
bool used[10]; //해당 숫자를 사용했는지 기록(visited와 유사)

bool nonZeroUsed() {
    for (int i = 0; i < 10; i++) {
        if (i && used[i]) {
            return true;
        }
    }
    return false;
}

void initialize() {
    cnt = 0;
    fill(begin(arr), end(arr), 0);
    fill(begin(used), end(used), false);
}

void dfs(int m) {
    if (cnt == 1000001) {
        return;
    }

    if (m == MAX) {
        for (int i = 0; i < MAX; i++) {
            answer[cnt][i] = arr[i];
        }
        cnt++;
        return;
    }

    for (int i = 0; i < 10; i++) {
        //used를 검사해서  visited에서 0 이외에 다른것을 썼는지 검사한다
        bool isNonZeroUsed = nonZeroUsed();
        
        // 001 002 는 되는데 400은 안되게 used를 변형시킨다.
        if (!isNonZeroUsed) {
            used[0] = false;
        }

        if (!used[i]) { 
            used[i] = true;
            //used를 또 검사해서  used에서 0 이외에 다른것을 썼는지 검사한다
            isNonZeroUsed = nonZeroUsed();
            //0이외의 것이 쓰이기전의 0과 이후의 0을 구별하자.
            if (!isNonZeroUsed) {
                arr[m] = -1;
            }
            else {
                arr[m] = i;
            }

            dfs(m + 1);
            used[i] = false;
        }
    }
}


// 메인 함수
int main() {
    int input;
    dfs(0);
    while (true) {
        // 숫자 입력
        cin >> input;

        // 입력된 숫자가 0이면 반복 종료
        if (input == 0) {
            break;
        }
        else {
            // 변수 및 배열 초기화 함수
            initialize();
            // 조건을 만족하는 수를 찾아서 출력
            for (int i = 0; i < MAX; i++) {
                if (answer[input][i] != -1) {
                    cout << answer[input][i];
                }
            }
            cout << '\n';
        }

    }
}

 

dfs (재귀) 로 먼저 1000000번째 까지의 반복하지 않는수에 관한 데이터를 이차원배열에 입력하고 시작했다.

 

매 입력때마다 이러한 연산을 반복하는건 시간초과를 초래한다.

매 테스트 케이스에서 변수 초기화에서 실수를 했다.

배열은 fill로 초기화를 진행하였다.

개인적으로 0을 처리하는게 이문제에서 가장 어려웠다

반복되지 않는 숫자는 used라는 boolean형 배열을 사용하면 쉽게 제거할 수 있지만,

0과 같은경우는. 001 과 100이 서로 다른 케이스다.

100은 세어지면 안되는것이고, 001은 0을 지워야한다.

전자의 경우는 used를 조작할 필요성이 있었고

후자의 경우는 arr에 -1을 마킹할 필요가 있었다.

이것을 해결해주는게 isNonZeroUsed 변수와 nonZeroUsed 함수이다.

지금 까지 방문한 숫자(노드) 에서 0만 있었는지, 혹은 다른 숫자가 있었는지 여부에 따라서,

그 0을 처리하는 방법이 달라야 하기 때문이다.

개인적으로 isNonZeroUsed가 이 문제의 핵심이지만 이게 제일 효율적인 방법인지는 모르겠다.

추가적으로 이 코드를 더 효율적으로 하기 위해선 

1000000번째 숫자까지 처음부터 구하고 시작하기보다는 

지금까지 나온 가장 큰 x번째를 저장하고, x번째보다 큰 입력이 나온다면 거기서부터 다시 재귀 호출을 시작하는게 더 효율적일 것이다.

그러나 내 생각으론 재귀호출을 멈췄다가 다시 진행하는건 arr와 used와 그리고 재귀 호출의 depth 까지 기억해야되서 (내 생각이 틀릴수도 있다) 이 문제가 요구하는것 이상의 구현일것같아서 (사실 귀찮아서) 그만 두었다.