13908번 비밀번호

 

 

 

www.acmicpc.net/problem/13908

13908번: 비밀번호

 

 

첫 번째 코드 : 백트래킹 - 추천

 

두 번째 코드 : int 숫자를 string 변환하면서, for문으로 모든 경우 다 탐색(개수를 셈하여 활용하는 방식) - 비추천

 

첫 번째 코드의 속도가 두 번째 코드의 속도보다 더 빠르다.

 

 

#include <bits/stdc++.h>

using namespace std;

int n, m, answer, a[10];
vector<int> v;

void bt(int idx)
{
    if (idx == n) {
        for (auto i : v) if (!a[i]) return;
        ++answer;
        return;
    }

    for (int i = 0; i <= 9; i++) {
        ++a[i];
        bt(idx + 1);
        --a[i];
    }
}

int main(void)
{
    cin.tie(0);
  
    scanf("%d %d", &n, &m);

    int num = 0;
    for (int i = 0; i < m; i++) {
        scanf("%d", &num);
        v.push_back(num);
    }

    bt(0);

    printf("%d\n", answer);
  
    return 0;
}

 

 

 

 

 

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> v;

string make_string(int number)
{
    string to_string_number = to_string(number);

    int len = to_string_number.length();

    if (len != n) {
        string zero = "";
        for (int i = 0; i < n - len; i++) {
            zero += "0";
        }
        to_string_number = zero + to_string_number;
    }

    return to_string_number;
}

bool isPassword(string s)
{
    for (auto i : v) {
        int cnt = count(s.begin(), s.end(), i + '0');
        if (cnt == 0) {
            return false;
        }
    }

    return true;
}

int main(void)
{
    cin.tie(0);

    int answer = 0;

    scanf("%d %d", &n, &m);

    int num = 0;
    for (int i = 0; i < m; i++) {
        scanf("%d", &num);
        v.push_back(num);
    }

    int goal = pow(10, n);

    for (int i = 0; i <= goal - 1; i++) {
        string str = make_string(i);
        if (isPassword(str)) {
            ++answer;
        }
    }

    printf("%d\n", answer);

    return 0;
}