{"id":34988,"date":"2024-11-01T09:34:19","date_gmt":"2024-11-01T09:34:19","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34988"},"modified":"2024-11-01T11:45:27","modified_gmt":"2024-11-01T11:45:27","slug":"course-on-kotlin-coding-test-finding-the-minimum-number-of-coins","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34988\/","title":{"rendered":"course on Kotlin coding test, finding the minimum number of coins"},"content":{"rendered":"<article>\n<header>\n<p>This article deals with an algorithm problem to find the minimum number of coins required, and it will explain the Kotlin code and process to solve it in detail.<\/p>\n<\/header>\n<section>\n<h2>Problem Description<\/h2>\n<p>When we have various coin values, we need to find the minimum number of coins required to make a specific amount. The goal is to minimize the number of coins needed to make the given amount.<\/p>\n<p><strong>Problem Input:<\/strong><\/p>\n<ul>\n<li>Number of coin types N (1 \u2264 N \u2264 100)<\/li>\n<li>Value of each coin A\u1d62 (1 \u2264 A\u1d62 \u2264 10,000)<\/li>\n<li>Target amount M (1 \u2264 M \u2264 1,000,000)<\/li>\n<\/ul>\n<p><strong>Problem Output:<\/strong><\/p>\n<p>Print the minimum number of coins required to make the target amount M. If it is not possible to make the amount, print -1.<\/p>\n<\/section>\n<section>\n<h2>Example<\/h2>\n<h3>Input Example:<\/h3>\n<pre>\n        3\n        1\n        3\n        4\n        6\n        <\/pre>\n<h3>Output Example:<\/h3>\n<pre>\n        2\n        <\/pre>\n<p>In the above example, there are 3 types of coins with values 1, 3, and 4. To make the target amount 6, we can use 2 coins by either (3 + 3) or (4 + 1 + 1).<\/p>\n<\/section>\n<section>\n<h2>Problem Solving Process<\/h2>\n<p>To solve this problem, we can use Dynamic Programming. Dynamic Programming is a technique to solve problems by reusing previous results, which can be very effectively applied in this problem.<\/p>\n<h3>1. Setting up the DP array<\/h3>\n<p>First, we declare a DP array to store the number of coins. DP[i] signifies the minimum number of coins needed to make amount i. During initialization, we set DP[0] to 0 and the rest to infinity (INF).<\/p>\n<h3>2. Defining the recurrence relation<\/h3>\n<p>We update the DP array by iterating over the values of each coin up to the amount M. Given a coin&#8217;s value, we start from that value and update the minimum number of coins for every possible amount.<\/p>\n<p>The recurrence relation is as follows:<\/p>\n<pre>\n        DP[j] = min(DP[j], DP[j - coin] + 1)\n        <\/pre>\n<p>Here, coin is the value of the currently considered coin.<\/p>\n<h3>3. Deriving the final result<\/h3>\n<p>After calculating the DP array for all coins and amounts, we check DP[M] to determine if that value is infinity (INF) or not. If it is infinity, we cannot make amount M, so we print -1; otherwise, we print the value of DP[M].<\/p>\n<\/section>\n<section>\n<h2>Code Implementation<\/h2>\n<pre><code>\nfun minCoins(coins: IntArray, target: Int): Int {\n    \/\/ Initialize the DP array to infinity\n    val dp = IntArray(target + 1) { Int.MAX_VALUE }\n    dp[0] = 0 \/\/ 0 coins are needed to make 0\n\n    \/\/ Update the DP array for each coin value\n    for (coin in coins) {\n        for (j in coin..target) {\n            if (dp[j - coin] != Int.MAX_VALUE) {\n                dp[j] = Math.min(dp[j], dp[j - coin] + 1)\n            }\n        }\n    }\n\n    \/\/ Check the result\n    return if (dp[target] == Int.MAX_VALUE) -1 else dp[target]\n}\n\nfun main() {\n    \/\/ Input values\n    val coins = intArrayOf(1, 3, 4)\n    val target = 6\n    val result = minCoins(coins, target)\n    println(result) \/\/ Output: 2\n}\n        <\/code><\/pre>\n<\/section>\n<section>\n<h2>Comparison and Optimization<\/h2>\n<p>The time complexity of this algorithm is O(N * M) and the space complexity is O(M). This algorithm is efficient in terms of time, especially when there are many coin types or the target amount is very large. However, there are ways to optimize the code further. For example, sorting the coin values in descending order and processing larger coins first can lead to faster results.<\/p>\n<\/section>\n<section>\n<h2>Various Cases<\/h2>\n<p>Here, we validate the performance of the algorithm through various input values. Testing different combinations of coin types and amounts to derive results is also an important step.<\/p>\n<h3>Case 1:<\/h3>\n<p><strong>Input:<\/strong> 4, 2, 5, 7, target amount = 14<\/p>\n<p><strong>Output:<\/strong> 2 (using 2 coins of 7)<\/p>\n<h3>Case 2:<\/h3>\n<p><strong>Input:<\/strong> 1, 3, 4, target amount = 11<\/p>\n<p><strong>Output:<\/strong> 3 (using 2 coins of 4 and 1 coin of 3)<\/p>\n<\/section>\n<footer>\n<p>This tutorial introduced how to find the minimum number of coins. We hope that you will grow as you solve algorithm problems. It is important to understand and apply the code and algorithm in practice. We hope this serves as a good example of how useful dynamic programming can be in solving problems.<\/p>\n<\/footer>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>This article deals with an algorithm problem to find the minimum number of coins required, and it will explain the Kotlin code and process to solve it in detail. Problem Description When we have various coin values, we need to find the minimum number of coins required to make a specific amount. The goal is &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34988\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;course on Kotlin coding test, finding the minimum number of coins&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[106],"tags":[],"class_list":["post-34988","post","type-post","status-publish","format-standard","hentry","category----en"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>course on Kotlin coding test, finding the minimum number of coins - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34988\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"course on Kotlin coding test, finding the minimum number of coins - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"This article deals with an algorithm problem to find the minimum number of coins required, and it will explain the Kotlin code and process to solve it in detail. Problem Description When we have various coin values, we need to find the minimum number of coins required to make a specific amount. The goal is &hellip; \ub354 \ubcf4\uae30 &quot;course on Kotlin coding test, finding the minimum number of coins&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34988\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:34:19+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:45:27+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34988\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34988\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"course on Kotlin coding test, finding the minimum number of coins\",\"datePublished\":\"2024-11-01T09:34:19+00:00\",\"dateModified\":\"2024-11-01T11:45:27+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34988\/\"},\"wordCount\":508,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Kotlin coding test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34988\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34988\/\",\"name\":\"course on Kotlin coding test, finding the minimum number of coins - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:34:19+00:00\",\"dateModified\":\"2024-11-01T11:45:27+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34988\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34988\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34988\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"course on Kotlin coding test, finding the minimum number of coins\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"course on Kotlin coding test, finding the minimum number of coins - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34988\/","og_locale":"ko_KR","og_type":"article","og_title":"course on Kotlin coding test, finding the minimum number of coins - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"This article deals with an algorithm problem to find the minimum number of coins required, and it will explain the Kotlin code and process to solve it in detail. Problem Description When we have various coin values, we need to find the minimum number of coins required to make a specific amount. The goal is &hellip; \ub354 \ubcf4\uae30 \"course on Kotlin coding test, finding the minimum number of coins\"","og_url":"https:\/\/atmokpo.com\/w\/34988\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:34:19+00:00","article_modified_time":"2024-11-01T11:45:27+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34988\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34988\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"course on Kotlin coding test, finding the minimum number of coins","datePublished":"2024-11-01T09:34:19+00:00","dateModified":"2024-11-01T11:45:27+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34988\/"},"wordCount":508,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Kotlin coding test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34988\/","url":"https:\/\/atmokpo.com\/w\/34988\/","name":"course on Kotlin coding test, finding the minimum number of coins - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:34:19+00:00","dateModified":"2024-11-01T11:45:27+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34988\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34988\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34988\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"course on Kotlin coding test, finding the minimum number of coins"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34988","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34988"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34988\/revisions"}],"predecessor-version":[{"id":34989,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34988\/revisions\/34989"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34988"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34988"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34988"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}