곱셈연산만 할 수 있어서 주어진 수의 약수만 필요로 하게 됩니다
저의 알고리즘은 모든 가능한 수를 구한 뒤 약수만 다시 걸러냅니다.
그 뒤 DFS 탐색을 합니다. 그 이유는 숫자의 길이가 있기 때문에 처음 구한 값이 최소가 보장되지 않습니다. 예를 들면 64라는 수를 구해야하고 2,3,8이 주어졋을 때 8*8= 총 4번에 가능하고 2*32= 총 5번에 가능합니다. 어느 방향으로 해야 최적인지 모르기 때문에 DFS로 풀었습니다.
처음 값 1과 0을 조심해서 풀었습니다. (무한루프 and Divide by zero)
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int T, n,p,button[10],check[10],res;
vector <int> v;
int cal(int x) {
int r=7;
if (x < 10) r = 1;
else if (x < 1e2) r = 2;
else if (x < 1e3) r = 3;
else if (x < 1e4) r = 4;
else if (x < 1e5) r = 5;
else if (x < 1e6) r = 6;
return r;
}
bool pos(int x) {
while (x) {
if (!check[x % 10]) return false;
x /= 10;
}
return true;
}
void dfs(int x,int sum) {
if (x == 1) {
res = res < sum ? res : sum;
return;
}
for (int i = 0; i < v.size(); i++)
if(x%v[i]==0) dfs(x/v[i], sum + cal(v[i])+1);
}
int main() {
scanf("%d", &T);
for (int tc = 1; tc <= T; tc++) {
queue <int> q;
v.clear();
res = 100;
p = 0;
for (int i = 0; i < 10; i++) {
scanf("%d", &n);
check[i] = n;
if (n) {
if (i) q.push(i);
button[p++] = i;
}
}
scanf("%d", &n);
if (pos(n)) res = cal(n)+1;
else {
while (!q.empty()) {
if (q.front() > n/10 ) break;
int x = q.front();
q.pop();
if (n%x == 0&&x!=1) v.push_back(x);
for (int i = 0; i < p; i++) {
int t = x * 10 + button[i];
if (t <= n) q.push(t);
}
}
while (!q.empty()) {
if (n%q.front() ==0) v.push_back(q.front());
q.pop();
}
dfs(n,0);
}
printf("#%d %d\n", tc, (res < 100 ? res : -1));
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기