[BOJ] 비밀번호 13908번 C++

 

문제

웅찬이는 근성이 대단한 도둑이다. 그래서 금고를 털 때, 모든 조합을 눌러본다. 예를 들어 비밀번호가 3글자 라는 사실을 알 때, 000, 001, 002, 003, … 998, 999의 모든 조합을 눌러본다. 그러나 웅찬이는 선견지명이 있어서 비밀번호에 어떤 숫자가 들어가는지 일부 알 수 있다. 예를 들어 3글자 비밀번호에 0이 들어감을 안다면 999 와 같이 0이 들어가지 않는 수는 가능성이 없다. 그러나 000, 012, 030과 같은 수는 가능하다. 비밀번호의 길이와 선견지명으로 알게된 비밀번호의 일부 숫자가 주어질 때, 모든 가능한 비밀번호의 개수를 출력하는 프로그램을 작성하시오.

입력

첫줄에 비밀번호의 길이 n (1 ≤ n ≤ 7), 선견지명으로 알게된 비밀번호에 들어가는 수 m(0 ≤ m ≤ n) 이 주어지고, 둘째 줄에 m개의 서로 다른 숫자(0~9)가 주어진다. m이 0인 경우 둘째 줄은 주어지지 않는다.

출력

 

가능한 모든 비밀번호의 개수를 출력한다.

 

접근 방식

비밀번호 길이가 최대 7개 이므로 모든 경우의 수의 개수는 7!이다

따라서 간단하게 브르트포스 알고리즘으로 구현이 가능하다

 

가능한 모든 비밀번호를 구하고 해당 비밀번호가 주어진 비밀번호의 숫자를 가지고 있는지 판단하면 된다!

처음에 어렵게 생각해서 오히려 꼬였던 문제다 .. :(

 

 

코드

#include<bits/stdc++.h>
using namespace std;

int n,m,ans = 0;
vector<int> v;


void sol(vector<int> pw) {
    if(pw.size() == n) {
        for(int i=0; i<m; i++) {
            if(find(pw.begin(), pw.end(), v[i]) == pw.end()) return;
        }
        ans++;
        return;
    }

    for(int i=0; i<=9; i++) {
        pw.push_back(i);
        sol(pw);
        pw.pop_back();
    }

}
int main() {
    cin>>n>>m;

    for(int i=0; i<m; i++) {
        int x; cin>>x;
        v.push_back(x);
    }
    vector<int> pw;
    sol(pw);
    cout<<ans;



}