CSES: Removing Digits

 Removing Digits

You are given an integer n$n$. On each step, you may subtract one of the digits from the number.

How many steps are required to make the number equal to 0$0$?

Input

The only input line has an integer n$n$.

Output

Print one integer: the minimum number of steps.

Constraints

• 1≤n≤106$1\le n\le {10}^6$
  

Example

Input:
27

Output:
5

Explanation: An optimal solution is 27→20→18→10→9→0$27\to 20\to 18\to 10\to 9\to 0$.

	/*
	1. function
	dp[i]: min step of to 0
	2. relation
	dp[i] = min(1 + dp(i - d))
	3. base
	dp[0] = 0
	*/
	int n;
	vi memo;
	vi get_digit(int x) {
	vi res;
	while (x > 0) {
	res.push_back(x % 10);
	x /= 10;
	}
	return res;
	}
	int dp(int i) {
	if (i == 0) return 0;
	if (memo[i] == -1) {
	vi digits = get_digit(i);
	int res = INT_MAX;
	for (auto d : digits) {
	if (d and i - d >= 0) res = min(res, 1 + dp(i - d));
	}
	memo[i] = res;
	}
	return memo[i];
	}
	void solve() {
	// in
	cin >> n;
	memo.resize(n + 1, -1);
	cout << dp(n) << endl;
	}

view raw Removing Digits.cpp hosted with ❤ by GitHub