브루트 포스 문제이다.
근데 진짜 빼박 브루트 포스로 전체 탐색을 돈다...
n자리 수 공간을 탐색하면서 꼭 들어가야 하는 숫자가 없으면 출력하지 않고 들어간다면 가능성 있는 비밀번호이므로 출력한다.
비교는 단순하게 string으로 바꿔 각 자리수를 비교했다. 숫자가 커진다면 스트링으로 확인할때 메모리 문제나 속도에 문제가 있을 수 있을것 같다. 속도가 문제라면 숫자 변수형이 아닌, 다른 자료구조를 사용해(배열이라던가...) 숫자가 사용되는지 여부를 확인할 수 있을 것 같다.
하지만 이 문제는 7자리가 끝이다. 허허... 빡 탐색으로 구현했다.
#include <iostream>
#include <string>
#include <vector>
int main()
{
int n, m, cnt = 0;
std::vector<int> knowing;
std::cin >> n >> m;
for (int i = 0; i < m; i++)
{
int tmp;
std::cin >> tmp;
knowing.push_back(tmp);
}
int max_len = 1;
for (int i = 0; i < n; i++)
{
max_len *= 10;
}
for (int i = 0; i< max_len; i++)
{
std::string tmp = std::to_string(i);
while (tmp.size() != n)
tmp = "0" + tmp;
bool available = true;
for (int k : knowing)
{
bool test = false;
for (char c : tmp)
{
if (c - '0' == k)
test = true;
}
if (!test)
{
available = false;
break;
}
}
if (available)
cnt++;
}
std::cout << cnt;
}
발생 가능한 모든 비밀번호를 탐색한다. 최대 10^7 크기의 공간을 탐색하고, 거기서 각 자리마다 입력받은 숫자가 맞는지 확인하므로 10진수 10 * 최대 7자리이므로 7을 곱하면, 7*10^8 공간이다. 이정도면 전체 탐색할만한것 같다.
좀 급해서 쉬운것 잡아봤다. 같은 골드5여도 이건 좀 쉬운 편인것 같다. 좀 어려운걸 잡아봐야겠다.
오늘도 평온한 하루가 되길. 슨민.
'짜잘한 기록' 카테고리의 다른 글
백준 15684 사다리 조작 (0) | 2021.12.01 |
---|---|
백준 1339 단어 수학 (0) | 2021.11.30 |
백준 1747 소수&팰린드롬 (0) | 2021.11.26 |
백준 1107 리모컨 (0) | 2021.11.25 |
백준 1759 암호 만들기 (0) | 2021.11.23 |