\uc624\ub298 \ub2e4\ub8f0 \ubb38\uc81c\ub294 \ub3d9\uc804 \uac70\uc2a4\ub984\ub3c8 \ubb38\uc81c<\/strong>\uc785\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \uc6b0\ub9ac\uac00 \ud604\uc2e4\uc5d0\uc11c \uc790\uc8fc \uc811\ud558\ub294 \ub2e4\uc591\ud55c \ub3d9\uc804\uc744 \uc774\uc6a9\ud574 \ud2b9\uc815 \uae08\uc561\uc744 \ub9cc\ub4e4 \ub54c, \uac00\uc7a5 \uc801\uc740 \uc218\uc758 \ub3d9\uc804\uc744 \uc0ac\uc6a9\ud558\ub294 \ubc29\ubc95\uc744 \ucc3e\ub294 \uac83\uc785\ub2c8\ub2e4.<\/p>\n \ub2e4\uc74c\uacfc \uac19\uc740 \uc870\uac74\uc744 \ub9cc\uc871\ud558\ub294 \ud568\uc218 \uc774 \ud568\uc218\ub294 \uc8fc\uc5b4\uc9c4 \uae08\uc561\uc744 \ub9cc\ub4e4\uae30 \uc704\ud574 \ud544\uc694\ud55c \ucd5c\uc18c \ub3d9\uc804\uc758 \uc218\ub97c \ubc18\ud658\ud574\uc57c \ud569\ub2c8\ub2e4. \ub3d9\uc804\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc5c6\ub294 \uacbd\uc6b0\uc5d0\ub294 \ubb38\uc81c\ub97c \uc880 \ub354 \uae4a\uc774 \uc788\uac8c \uc774\ud574\ud558\uae30 \uc704\ud574 \uba87 \uac00\uc9c0 \uc608\uc81c\ub97c \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uaca0\uc2b5\ub2c8\ub2e4. \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc740 \ud604\uc7ac \uc0c1\ud669\uc5d0\uc11c \uac00\uc7a5 \ucd5c\uc801\uc778 \uc120\ud0dd\uc744 \ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \ub3d9\uc791\ud569\ub2c8\ub2e4. \ub530\ub77c\uc11c, \uc6b0\ub9ac\ub294 \uac00\uc7a5 \ud070 \ub3d9\uc804\ubd80\ud130 \ucc28\ub840\ub300\ub85c \uc0ac\uc6a9\ud558\uc5ec \ubaa9\ud45c \uae08\uc561\uc744 \ub9cc\ub4dc\ub294 \ubc29\ubc95\uc744 \ubaa8\uc0c9\ud558\ub824 \ud569\ub2c8\ub2e4.<\/p>\n \ud574\ub2f9 \uc54c\uace0\ub9ac\uc998\uc758 \uad6c\uccb4\uc801\uc778 \ub2e8\uacc4\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n \uadf8\ub7fc \uc774 \uc811\uadfc \ubc29\ubc95\uc744 \ubc14\ud0d5\uc73c\ub85c \ucf54\ub4dc\ub97c \uc791\uc131\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n \uc774\uc81c \uc791\uc131\ud55c \ud568\uc218\ub97c \ud14c\uc2a4\ud2b8\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc774\ub7ec\ud55c \ubc29\uc2dd\uc73c\ub85c \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ub3d9\uc804 \uac70\uc2a4\ub984\ub3c8 \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\uc5c8\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub97c \ud1b5\ud574 \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc758 \uae30\ucd08\uc801\uc778 \uc811\uadfc \ubc29\uc2dd\uc744 \uc775\ud788\uace0, \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \ud754\ud788 \ub098\uc624\ub294 \ubb38\uc81c \uc720\ud615\uc744 \uacf5\ubd80\ud588\uc2b5\ub2c8\ub2e4.<\/p>\n \uc55e\uc73c\ub85c \ub354 \ub9ce\uc740 \ubb38\uc81c\ub97c \uc5f0\uc2b5\ud558\uba70 \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud55c \uc774\ud574\ub97c \uae4a\uc774\uac8c \uc313\uc544\uac00\uae38 \ubc14\ub78d\ub2c8\ub2e4. \uc704\uc758 \ubb38\uc81c\uc640 \uac19\uc774, \ub370\uc774\ud130\ub97c \uc5b4\ub5bb\uac8c \uc815\ub82c\ud558\uace0, \ubc18\ubcf5\ubb38\uc744 \ud65c\uc6a9\ud558\uc5ec \ud574\uacb0\ucc45\uc744 \ucc3e\uc544\ub098\uac00\ub294\uc9c0\uc5d0 \ub300\ud55c \uc5f0\uc2b5\uc774 \ud544\uc694\ud569\ub2c8\ub2e4. \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc591\ud55c \ubb38\uc81c \ud574\uacb0\uc5d0 \uc720\uc6a9\ud55c \ub3c4\uad6c\uac00 \ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \uac10\uc0ac\ud569\ub2c8\ub2e4!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"\ubb38\uc81c \uc815\uc758<\/h3>\n
min_coins(coins, amount)<\/code>\ub97c \uc791\uc131\ud558\uc2dc\uc624:<\/p>\n\n
coins<\/code>: \uc0ac\uc6a9 \uac00\ub2a5\ud55c \ub3d9\uc804\uc758 \ubaa9\ub85d (\uc608: [1, 5, 10, 25])<\/li>\namount<\/code>: \ub9cc\ub4e4\uace0\uc790 \ud558\ub294 \uae08\uc561<\/li>\n<\/ul>\n-1<\/code>\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4.<\/p>\n\ubb38\uc81c \uc774\ud574\ud558\uae30<\/h2>\n
\n \uc785\ub825: coins = [1, 5, 10, 25], amount = 63<\/code>
\n \ucd9c\ub825: 6<\/code>
\n \uc124\uba85: 25 + 25 + 10 + 1 + 1 + 1 = 63\n <\/div>\n
\n \uc785\ub825: coins = [2, 4], amount = 5<\/code>
\n \ucd9c\ub825: -1<\/code>
\n \uc124\uba85: 5\ub97c \ub9cc\ub4e4 \uc218 \uc788\ub294 \ubc29\ubc95\uc774 \uc5c6\uc74c.\n <\/div>\n\uc811\uadfc \ubc29\ubc95<\/h2>\n
\n
-1<\/code>\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n\ucf54\ub4dc \uad6c\ud604<\/h2>\n
\ndef min_coins(coins, amount):\n # \ub3d9\uc804\uc744 \ub0b4\ub9bc\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\n coins.sort(reverse=True)\n \n count = 0 # \uc0ac\uc6a9\ud55c \ub3d9\uc804\uc758 \uc218\n \n for coin in coins:\n # \ud604\uc7ac \ub3d9\uc804\uc774 amount\ubcf4\ub2e4 \ud070 \uacbd\uc6b0 \ubb34\uc2dc\n while amount >= coin:\n amount -= coin # \ub3d9\uc804\uc758 \uac00\uce58\ub97c amount\uc5d0\uc11c \ube7c\uae30\n count += 1 # \ub3d9\uc804 \uac1c\uc218 \uc99d\uac00\n \n # \ucd5c\uc885\uc801\uc73c\ub85c amount\uac00 0\uc778\uc9c0 \ud655\uc778\n return count if amount == 0 else -1\n <\/code><\/pre>\n\ud14c\uc2a4\ud2b8<\/h2>\n
\n# \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\nprint(min_coins([1, 5, 10, 25], 63)) # 6\nprint(min_coins([2, 4], 5)) # -1\nprint(min_coins([5, 2, 1], 11)) # 3 (5 + 5 + 1)\n <\/code><\/pre>\n\uacb0\ub860<\/h2>\n