Hello, everyone preparing for the coding test! In this course, we will solve an algorithm problem titled “Finding the Minimum Number of Coins,” and I will explain the detailed solution process. This problem will greatly help you understand algorithms and develop logical thinking.<\/p>\n
To purchase items at a store, a specific amount of money is required. However, we may have limitations on the types and quantities of coins we possess. The goal of this problem is to find a way to minimize the number of coins used to create a specific amount using the available coin denominations.<\/p>\n
Here is an example of the problem:<\/p>\n
In this case, we need to find a way to make 125 won with the minimum number of coins.<\/p>\n
This problem is a typical greedy algorithm problem. A greedy algorithm solves a problem by making the best choice at each step.<\/p>\n
The specific steps for solving the problem are as follows:<\/p>\n
Now, let\u2019s implement the C# code based on the above approach.<\/p>\n
\n\nusing System;\n\nclass Program\n{\n static void Main(string[] args)\n {\n \/\/ Types of coins\n int[] coins = new int[] { 100, 50, 10, 5, 1 };\n \/\/ Target amount\n int targetAmount = 125;\n \n \/\/ Number of coins\n int totalCoins = 0;\n\n \/\/ Making amount with coins\n for (int i = 0; i < coins.Length; i++)\n {\n \/\/ Maximum number of coins that can be used\n while (targetAmount >= coins[i])\n {\n targetAmount -= coins[i];\n totalCoins++;\n }\n }\n\n \/\/ Output result\n Console.WriteLine(\"Minimum number of coins: \" + totalCoins);\n }\n}\n<\/code>\n<\/pre>\nCode Explanation<\/h3>\n\n- First, the required types of coins are initialized in an array.<\/li>\n
- The amount to be used is stored in a variable, and the totalCoins variable is declared to count the number of coins.<\/li>\n
- For each coin, if the amount is greater than the coin’s value, the coin is used, and the coin count is increased.<\/li>\n
- Finally, the minimum number of coins is printed to the console.<\/li>\n<\/ul>\n
Code Execution Result<\/h2>\n
Running the above code will produce the following result:<\/p>\n
\n\nMinimum number of coins: 3\n<\/code>\n<\/pre>\nWe can see that at least 3 coins must be used to create 125 won with the given combinations of coins. For example, using one 100 won coin, one 5 won coin, and one 1 won coin would yield a valid combination.<\/p>\n
Summary of the Problem-Solving Process<\/h2>\n