[백준 13908] 비밀번호 (C++)

문제 링크: www.acmicpc.net/problem/13908

13908번: 비밀번호

1. 주의할 점

- 메모리 제한이 있으므로 Set을 이용하지 않도록 한다

 

2. 구현

- 7!의 연산을 수행해도 1초에 도달하지 못하기 때문에 브루트포스로 접근해도 상관없다(상황마다 다르지만, 약 10!가 1초로 알고있습니다)

- 필요로 하는 수를 V 벡터에 담는다

- DFS()를 수행하며 Str의 길이가 N이 되었다면 V에서 필요로 하는 모든 수가 Str에 있는지 확인한다. 만약 전부 있다면 Cnt++한다. 구현한 DFS는 숫자가 증가하는 방향이므로, 예제의 77과 같은 경우도 1번만 도달합니다

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int len, num, val, cnt = 0;
vector<int> v;

void dfs(int idx, string str) {
	if(idx == len) {
		bool avail = true;
		for (int i = 0; i < v.size(); i++) {
			bool temp = false;
			for (int j = 0; j < str.size(); j++) {
				if (str[j] - '0' == v[i]) {
					temp = true;
					break;
				}
			}
			if (!temp) {
				avail = false;
				break;
			}
		}
		if (avail) {
			cnt++;
			cout << str << endl;
		}
		return;
	}
	for (int i = 0; i < 10; i++) {
		char c = i + '0';
		dfs(idx + 1, str + c);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> len >> num;
	for (int i = 0; i < num; i++) {
		cin >> val;
		v.push_back(val);
	}
	dfs(0, "");
	cout << cnt;
	return 0;
}