# [Silver II] 비밀번호 [문제 링크](https://www.acmicpc.net/problem/13908) ## 문제 설명 <p>웅찬이는 근성이 대단한 도둑이다. 그래서 금고를 털 때, 모든 조합을 눌러본다. 예를 들어 비밀번호가 3글자 라는 사실을 알 때, 000, 001, 002, 003, … 998, 999의 모든 조합을 눌러본다. 그러나 웅찬이는 선견지명이 있어서 비밀번호에 어떤 숫자가 들어가는지 일부 알 수 있다. 예를 들어 3글자 비밀번호에 0이 들어감을 안다면 999 와 같이 0이 들어가지 않는 수는 가능성이 없다. 그러나 000, 012, 030과 같은 수는 가능하다. 비밀번호의 길이와 선견지명으로 알게된 비밀번호의 일부 숫자가 주어질 때, 모든 가능한 비밀번호의 개수를 출력하는 프로그램을 작성하시오.</p> ## 입력 <p>첫줄에 비밀번호의 길이 n (1 ≤ n ≤ 7), 선견지명으로 알게된 비밀번호에 들어가는 수 m(0 ≤ m ≤ n) 이 주어지고, 둘째 줄에 m개의 서로 다른 숫자(0~9)가 주어진다. m이 0인 경우 둘째 줄은 주어지지 않는다.</p> ## 출력 <p>가능한 모든 비밀번호의 개수를 출력한다.</p> ## 풀이 백트래킹으로 모든 경우의 수를 구했습니다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 10'000'001; bool exist[MAX]; int n, m, arr[7]; void back(int depth=0, string s="") { if(depth==n) { for(int i=0;i<m;i++) { bool chk=false; for(int j=0;j<n;j++) { if(arr[i]==s[j]-'0') chk=true; } if(!chk) return; } exist[stoi(s)]=true; return; } for(int i=0;i<=9;i++) back(depth+1, s+to_string(i)); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i=0;i<m;i++) cin >> arr[i]; back(); cout << accumulate(exist, exist+MAX, 0); } ```