For example, 123, 321, and 456 are stair numbers. However, 122, 200, and 300 are not stair numbers.<\/li>\n<\/ul>\n\n Given an integer N<\/code>, the problem is to find the number of stair numbers consisting of N<\/code> digits. I will explain how to calculate the output value considering the input value N<\/code>.\n <\/p>\n2. Problem Rules<\/h2>\n
\n – The maximum number of digits in input is 100, and when N<\/code> is 1, there are 10 stair numbers including 0 to 9.
\n – Each digit can be considered a number from 0 to 9, and the first digit cannot be 0.
\n – As the number of digits increases, the combinations of stair numbers increase.\n <\/p>\n3. Solution Strategy<\/h2>\n
\n This problem can be solved using dynamic programming. The basic idea is to store the number of possible stair numbers for each digit and use it to calculate the number of stair numbers for the next digit.\n <\/p>\n
\n- For each digit, consider the possible last digit and calculate a new value based on the value from the previous digit.<\/li>\n
- For example,
dp[n][digit]<\/code> is an array that stores the number of stair numbers when the last digit of an n-digit number is digit<\/code>.<\/li>\n- Therefore,
dp[n][digit]<\/code> can be calculated as the sum of dp[n-1][digit-1]<\/code> and dp[n-1][digit+1]<\/code>.<\/li>\n<\/ul>\n3.1. Recurrence Relation<\/h3>\n
\n The dp array can be constructed using the following recurrence relations.\n <\/p>\n
\n dp[n][0] = dp[n-1][1]\n dp[n][9] = dp[n-1][8]\n dp[n][digit] = dp[n-1][digit-1] + dp[n-1][digit+1] (1 <= digit <= 8)\n <\/code><\/pre>\n4. Code Implementation<\/h2>\n
\n Now, let’s implement the code to solve the problem. Below is the code using Kotlin.\n <\/p>\n
\n fun countStairNumbers(n: Int): Int {\n if (n == 1) return 10 \/\/ When N is 1, the stair numbers are from 0 to 9.\n\n val mod = 1000000000 \/\/ Modular operation used when outputting the result\n val dp = Array(n + 1) { IntArray(10) }\n\n \/\/ Initial values\n for (j in 1..9) {\n dp[1][j] = 1 \/\/ The first digit can be from 1 to 9\n }\n\n \/\/ Constructing the DP array\n for (i in 2..n) {\n for (j in 0..9) {\n if (j == 0) {\n dp[i][j] = dp[i - 1][1] \/\/ 0 is only possible from 1 in the previous digit\n } else if (j == 9) {\n dp[i][j] = dp[i - 1][8] \/\/ 9 is only possible from 8 in the previous digit\n } else {\n dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod\n }\n }\n }\n\n \/\/ Calculating total stair numbers\n var result = 0\n for (j in 0..9) {\n result = (result + dp[n][j]) % mod\n }\n\n return result\n }\n\n fun main() {\n val n = readLine()!!.toInt() \/\/ Receiving input value\n println(countStairNumbers(n)) \/\/ Outputting the stair numbers\n }\n <\/code><\/pre>\n5. Execution and Results<\/h2>\n
\n Running the above code will output the number of stair numbers based on the input N value. Below are the results for some test cases.\n <\/p>\n
\n- Input: 1 \u2192 Output: 10<\/li>\n
- Input: 2 \u2192 Output: 17<\/li>\n
- Input: 3 \u2192 Output: 32<\/li>\n<\/ul>\n
\n It can be confirmed that the number of stair numbers is correctly calculated for each input value.\n <\/p>\n
6. Conclusion<\/h2>\n
\n In this tutorial, we used dynamic programming to solve the ‘Counting Stair Numbers’ problem. We examined how to construct the recurrence relations and the DP array during the problem-solving process, and wrote the actual code. Such problems are frequently presented in coding tests, so it is important to practice adequately.\n <\/p>\n
\n We will continue to tackle various algorithm problems in the future, and hope to help you improve your problem-solving skills through Kotlin. Thank you!\n <\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
Today, we will solve an interesting algorithm problem called ‘Counting Stair Numbers’ using Kotlin. In this tutorial, we will explain the definition of the problem, the rules, the solution strategy, and the process of implementing the code in detail. The topics covered are as follows. 1. Problem Definition Stair numbers are defined based on the … \ub354 \ubcf4\uae30 “kotlin coding test course, calculating the number of steps”<\/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-34950","post","type-post","status-publish","format-standard","hentry","category----en"],"yoast_head":"\nkotlin coding test course, calculating the number of steps - \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\/34950\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"kotlin coding test course, calculating the number of steps - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Today, we will solve an interesting algorithm problem called ‘Counting Stair Numbers’ using Kotlin. In this tutorial, we will explain the definition of the problem, the rules, the solution strategy, and the process of implementing the code in detail. The topics covered are as follows. 1. Problem Definition Stair numbers are defined based on the … \ub354 \ubcf4\uae30 "kotlin coding test course, calculating the number of steps"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34950\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:33:55+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:45:36+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\/34950\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34950\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"kotlin coding test course, calculating the number of steps\",\"datePublished\":\"2024-11-01T09:33:55+00:00\",\"dateModified\":\"2024-11-01T11:45:36+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34950\/\"},\"wordCount\":424,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Kotlin coding test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34950\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34950\/\",\"name\":\"kotlin coding test course, calculating the number of steps - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:33:55+00:00\",\"dateModified\":\"2024-11-01T11:45:36+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34950\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34950\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34950\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"kotlin coding test course, calculating the number of steps\"}]},{\"@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":"kotlin coding test course, calculating the number of steps - \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\/34950\/","og_locale":"ko_KR","og_type":"article","og_title":"kotlin coding test course, calculating the number of steps - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Today, we will solve an interesting algorithm problem called ‘Counting Stair Numbers’ using Kotlin. In this tutorial, we will explain the definition of the problem, the rules, the solution strategy, and the process of implementing the code in detail. The topics covered are as follows. 1. Problem Definition Stair numbers are defined based on the … \ub354 \ubcf4\uae30 \"kotlin coding test course, calculating the number of steps\"","og_url":"https:\/\/atmokpo.com\/w\/34950\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:33:55+00:00","article_modified_time":"2024-11-01T11:45:36+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\/34950\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34950\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"kotlin coding test course, calculating the number of steps","datePublished":"2024-11-01T09:33:55+00:00","dateModified":"2024-11-01T11:45:36+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34950\/"},"wordCount":424,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Kotlin coding test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34950\/","url":"https:\/\/atmokpo.com\/w\/34950\/","name":"kotlin coding test course, calculating the number of steps - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:33:55+00:00","dateModified":"2024-11-01T11:45:36+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34950\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34950\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34950\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"kotlin coding test course, calculating the number of steps"}]},{"@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\/34950","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=34950"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34950\/revisions"}],"predecessor-version":[{"id":34951,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34950\/revisions\/34951"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34950"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34950"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34950"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}