Brute Force(Complete Search : 완전 탐색)를 시도해야 하는 경우는 두가지 이다.
ICPC에서는 문제를 풀 때 완전 탐색을 가장 먼저 고려해보아야 한다. 생각해 내기도 쉽고 코딩 및 디버깅도 쉽기 때문이다. Keep It Short and Simple(KISS) 원칙을 기억하자. 최소한 서브태스크 제도가 있다면 최소 점수라도 받을 수 있다.
UVa 725 - Division
fghij가 01234qnxj 98765 사이의 범위 안에 있어야 한다는 것을 금방 알 수 있다. 따라서 최대 10만가지 정도의 경우가 존재한다. 범위를 좀 더 좁혀보면 fghij는 01234부터 98765 / N 사이에 있어야 한다. 경우의 수는 N = 2일 때 5만 정도로 최대가 되고 N이 커지면 더 줄어든다.
fghij를 결정하고 나면 fghij * N을 계산하여 abcde를 얻을 수 있고, 그 다음에는 사용된 10개의 숫자가 모두 다른지 확인해보면 된다.
이를 이중 루프로 구현할 수 있고, 시간 복잡도를 분석해보면 각 test case마다 5만 * 10 = 50만번 정도의 연산만 필요하다. 이는 작은 값이며, 따라서 반복적 완전 탐색 풀이를 써도 된다.
비트 연산 트릭을 사용했다.
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
void solve(int n) {
bool flag = false;
for (int fghij = 1234; fghij <= 98765 / n; fghij++) {
int abcde = fghij * n;
int tmp, used = (fghij < 10000);
tmp = abcde;
while (tmp) {
// tmp의 마지막 자리수를 비트마스크집합에 놓는 과정이다.
used |= 1 << (tmp % 10);
tmp /= 10;
}
tmp = fghij;
while (tmp) {
// tmp의 마지막 자리수를 비트마스크집합에 놓는 과정이다.
used |= 1 << (tmp % 10);
tmp /= 10;
}
// 크기가 10인 비트마스크의 모든 원소가 켜졌는지 확인하는 연산이다.
if (used == (1 << 10) - 1) {
flag = true;
printf("%0.5d / %0.5d = %d\\n", abcde, fghij, n);
}
}
if (flag == false)
printf("There are no solutions for %d.\\n\\n", n);
}
int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
int t;
while (1) {
cin >> t;
if (t == 0) {
return -1;
}
solve(t);
}
}
https://s3-us-west-2.amazonaws.com/secure.notion-static.com/149e717d-7a32-4b5b-b585-21e22758d56e/p441.pdf
구해야 할 부분집합의 크기가 6으로 고정되어 있고 결과를 사전식으로 출력해야 하므로 가장 쉬운 풀이는 6중 루프를 사용하는 것이다. $k$가 가장 큰 경우에도 6중 루프가 출력하는 내용은 ${12}\mathrm{C}{6} = 924$ 으로 아주 작은 값이다.
// UVa441 - Lotto
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
void solve(int n) {
vi data(n);
for (auto &s : data) {
cin >> s;
}
for (int a = 0; a < n - 5; a++) {
for (int b = a + 1; b < n - 4; b++) {
for (int c = b + 1; c < n - 3; c++) {
for (int d = c + 1; d < n - 2; d++) {
for (int e = d + 1; e < n - 1; e++) {
for (int f = e + 1; f < n; f++) {
printf("%d %d %d %d %d %d\\n",
data[a], data[b], data[c], data[d], data[e], data[f]);
}
}
}
}
}
}
cout << '\\n';
}
int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
int t;
while (1) {
cin >> t;
if (t == 0) {
return -1;
}
solve(t);
}
}