BOJ : 13908 비밀번호

---

[BOJ 13908(G5)리뷰]

오랜만에 브루트포스 문제를 풀었다.

숫자는 0~9까지의 수이므로 총 10개이고, 최대 비밀번호의 길이가 7이므로 O(10^7)의 연산으로 모든 경우를 탐색할 수 있다. 1천만 정도 되는 연산량 이므로 1초내에 충분히 계산이 가능하다.

백트래킹으로 코드를 짰으며 따로 값들을 저장하지 않고 숫자 사용여부만 체크해주면서 올라가면 된다.
결국 길이가 n이 되었을때 반드시 들어가야 하는 숫자들이 사용되었는지 확인하고 다 사용되었다면 정답의 갯수를 늘려주면 된다.

/*
	21.02.08
	BOJ : 13908 비밀번호 (https://www.acmicpc.net/problem/13908)
	백트래킹/브루트포스
*/
#include <bits/stdc++.h>

using namespace std;

int n, m;
int num[7];
int check[10];
int ans = 0;

void dfs(int cur) {
	if (cur == n) {
		//검사
		for (int i = 0; i < m; i++) {
			if (check[num[i]] == 0)
				return;
		}
		ans++;
		return;
	}

	for (int i = 0; i <= 9; i++) {
		check[i]++;
		dfs(cur + 1);
		check[i]--;
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> num[i];
	}

	dfs(0);

	cout << ans;
	
	return 0;
}