Advertisement
Josif_tepe

Untitled

Mar 18th, 2021
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.64 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. int memo[1000006];
  5. int f(int x) {
  6.     if(x == 0) {
  7.         return 0;
  8.     }
  9.     if(memo[x] != -1) {
  10.         return memo[x];
  11.     }
  12.     int tmp = x;
  13.     int najmal_broj_pati = 2000000;
  14.     while(tmp > 0) {
  15.         int cifra = tmp % 10;
  16.         if(cifra != 0) {
  17.             najmal_broj_pati = min(najmal_broj_pati, f(x - cifra) + 1);
  18.         }
  19.         tmp /= 10;
  20.     }
  21.     memo[x] = najmal_broj_pati;
  22.     return najmal_broj_pati;
  23. }
  24. int main()
  25. {
  26.     int n;
  27.     cin >> n;
  28.     for(int i = 0; i <= n; i++)
  29.     {
  30.         memo[i] = -1;
  31.     }
  32.     cout << f(n) << endl;
  33.    
  34.     return 0;
  35. }
  36.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement