#include <iostream> #include <vector> using namespace std; class Solution { public: int buyNails(vector<int>& nails, int count) { vector<int> dp(count + 1, -1); dp[0] = 0; for (int i = 1; i <= count; i++) { for (int j = 0; j < nails.size(); j++) { if (i - nails[j] >= 0 && dp[i - nails[j]] != -1) { if (dp[i] == -1 || dp[i] > dp[i - nails[j]] + 1) dp[i] = dp[i - nails[j]] + 1; } } } return dp[count]; } }; int main() { vector<int> nails = { 4, 9 }; int n; cin >> n; Solution s; cout << s.buyNails(nails, n) << endl;; return 0; }