PlaygroundCpp/Sources/Playground.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <climits>
//#include <gtest/gtest.h>

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';
}