removing_digits_1637.cpp (500B)
1 #include <algorithm> 2 #include <iostream> 3 #include <vector> 4 5 static constexpr int inf = 1999999999; 6 7 std::vector<int> digits(int n) { 8 std::vector<int> d; 9 for (int i = n; i != 0; i /= 10) 10 d.push_back(i % 10); 11 return d; 12 } 13 14 int f(std::vector<int>& a, int n) { 15 if (a[n] != inf) return a[n]; 16 for (auto d : digits(n)) 17 if (d != 0) 18 a[n] = std::min(a[n], 1+f(a, n-d)); 19 return a[n]; 20 } 21 22 int main() { 23 int n; 24 std::cin >> n; 25 std::vector<int> a(n+1, inf); 26 a[0] = 0; 27 std::cout << f(a, n) << "\n"; 28 }