#include #include //#include int getChange(int money) { // denominations: 1, 3, 4 int denominations[3] = { 1, 3, 4 }; int minNumCoins[money + 1] = { }; for (int m = 1; m < money + 1; m++) { minNumCoins[m] = INT_MAX; for (int i = 0; i < 3; i++) { if (m >= denominations[i]) { int numCoins = minNumCoins[m - denominations[i]] + 1; if (numCoins < minNumCoins[m]) { minNumCoins[m] = numCoins; } } } } return minNumCoins[money]; } //TEST(SortPoint, Sort1) { // ASSERT_EQ(2, getChange(2)); // ASSERT_EQ(9, getChange(34)); //} int main() { int m; std::cin >> m; std::cout << getChange(m) << '\n'; }