(C++) - 백준(BOJ) 13908번 : 비밀번호

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

13908번: 비밀번호

brute force 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 1. n , m, 알고있는 숫자정보를 저장할 일차원 배열 know를 선언합니다. 2. n, m을 입력 후 m만큼 알고있는 숫자정보를 입력합니다. 해당 정보를 index로 해서 know[숫자] = 1로 저장합니다.

 

📔 풀이과정

dfs함수를 수행합니다.

 1. n개의 길이만큼 0 ~ 9사이의 수를 뽑습니다.

 

 2. 0 ~ 9까지 loop를 돌며 know[i] = 1인 경우 뽑은 수에 i가 있는지 확인합니다. 만약 없다면 유효하지 않으므로 재귀를 종료합니다.

 

 3. ans에 유효한 숫자를 push_back해줍니다.

 

📔 정답출력

담겨있는 ans의 size를 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, m, know[10];
vector <char> v;
vector <int> ans;
void dfs(int depth){
    if(depth == n){
        string tmp = "";
        for(int i = 0; i < 10; i++){
            if(know[i]){
                int flag = 0;
                for(auto e : v){
                    if(e - '0' == i) {flag = 1; break;}
                }
                if(!flag) return;
            }
        }
        for(auto e : v) tmp += e;
        ans.push_back(stoi(tmp));
        return;
    }
    for(int i = 0; i <= 9; i++){
        v.push_back(i + '0');
        dfs(depth + 1);
        v.pop_back();
    }
}
int main(){
    cin >> n >> m;
    for(int i = 0, x; i < m; i++){
        cin >> x;
        know[x] = 1;
    }
    dfs(0);
    cout << ans.size();
}