BOJ 1443 - 망가진 계산기

BOJ 1443 - 망가진 계산기

모든 경우의 수는 $8H{30}=\dbinom{37}{8}=38608020$ 이다.

적절한 백트랙킹이 가능하므로 더 빨리 돈다.

int ans = -1, d;
inline int get_len(int d) {
   if (d == 0) return 0;
   int ret = 0;
   while (d) {
      d /= 10;
      ret++;
   }
   return ret;
}
void fn(int p, int len, int last, int cur) {
   if (len > d) return;
   if (p == 0) {
      ans = max(ans, cur);
      return;
   }
   for (int d = last; d <= 9; d++) {
      int nxt = cur * d;
      int next_len = len != get_len(nxt) ? len + 1 : len;
      fn(p - 1, next_len, d, nxt);
   }
}

void solve() {
   int p;
   cin >> d >> p;
   fn(p, 1, 2, 1);
   cout << ans;
}