[C++] 반복하지 않는 수 (백준 7696번)

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

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;

        int i = 1;
        while (i <= n) {
            int tmp = i;
            bool eq = false;
            vector<bool> chk(10, false);
            while (tmp > 0) {
                if (chk[tmp % 10]) {
                    eq = true;
                    break;
                } else {
                    chk[tmp % 10] = true;
                    tmp /= 10;
                }
            }
            if (eq) {
                n++;
            }
            i++;
        }

        cout << n << '\n';
    }
}

처음엔 브루트포스라길래 이렇게 무식하게 1부터 하나씩 보면서 반복되는 수가 존재하는지 아닌지 확인하도록 코드를 짰다. 당연하게도? 시간 초과가 났다. (오답)

 

#include <iostream>
#include <vector>
using namespace std;

vector<bool> chk;
int cnt, n, ans;
bool isfin;

void dfs(int idx, int res, int fin) {
    if (idx == fin) {
        cnt++;
        if (cnt == n) {
            isfin = true;
            ans = res;
        }
        return;
    }
    if (idx == 0) {
        for (int i = 1; i < 10; i++) {
            if (!chk[i]) {
                chk[i] = true;
                dfs(idx + 1, res * 10 + i, fin);
                chk[i] = false;
            }
            if (isfin) break;
        }
    } else {
        for (int i = 0; i < 10; i++) {
            if (!chk[i]) {
                chk[i] = true;
                dfs(idx + 1, res * 10 + i, fin);
                chk[i] = false;
            }
            if (isfin) break;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while (true) {
        cin >> n;
        if (n == 0) break;

        isfin = false;
        cnt = 0;
        ans = 0;
        for (int i = 1; i <= 10; i++) {
            chk = vector<bool>(10, false);
            dfs(0, 0, i);
            if (isfin) break;
        }

        cout << ans << '\n';
    }
}

그 다음에 꽤 많이 헤매다가 (ㅎㅎ) 백트래킹으로 겨우 풀었다. 뭔가 사소하게 체크할 게 좀 많아서 좀 걸렸다. 이게 뭐라고 이렇게 시간을 많이 썼지... (정답)