\uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc740 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc5d0\uc11c \ud56d\uc0c1 \ucd5c\uc801\uc758 \uc120\ud0dd\uc744 \ud558\ub294 \ubc29\uc2dd\uc73c\ub85c, \uc2e4\uc2dc\uac04\uc73c\ub85c \ud604\uc7ac \uc0c1\ud0dc\uc5d0\uc11c \uac00\uc7a5 \uc88b\uc740 \uc120\ud0dd\uc744 \ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4. \ubcf8 \uac15\uc88c\uc5d0\uc11c\ub294 \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc758 \uae30\ubcf8 \uac1c\ub150 \ubc0f \uc608\uc81c\ub97c \ud1b5\ud574 \uc774\ud574\ub97c \ub3d5\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n<\/header>\n \uc0c1\uc810\uc5d0\uc11c \uc81c\uacf5\ud558\ub294 \ub3d9\uc804\uc758 \uc885\ub958\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \uc8fc\uc5b4\uc9c4 \uae08\uc561\uc744 \uac70\uc2ac\ub7ec \uc8fc\uae30 \uc704\ud55c \ucd5c\uc18c\ud55c\uc758 \ub3d9\uc804 \uac1c\uc218\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.<\/p>\n \ubb38\uc81c \uc124\uba85:<\/strong><\/p>\n \uc785\ub825 \uc608\uc2dc:<\/strong><\/p>\n \ucd9c\ub825 \uc608\uc2dc:<\/strong><\/p>\n \uac70\uc2ac\ub7ec \uc904 \uae08\uc561\uc744 \ub3d9\uc804\uc758 \uc885\ub958\uc5d0 \ub530\ub77c \ucd5c\uc18c\ud55c\uc758 \ub3d9\uc804 \uac1c\uc218\ub85c \ud45c\ud604\ud558\ub294 \uac83\uc774 \uc774 \ubb38\uc81c\uc758 \ud575\uc2ec\uc785\ub2c8\ub2e4. \uac00\uc7a5 \ud070 \ub3d9\uc804\ubd80\ud130 \uc120\ud0dd\ud558\ub294 \ubc29\ubc95\uc774 \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.<\/p>\n \ud574\uacb0\uc744 \uc704\ud574 \uc0ac\uc6a9\ud560 \uae30\ubcf8\uc801\uc778 \uc811\uadfc \ubc29\ubc95\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n \uc704\uc758 \ucf54\ub4dc\uc5d0\uc11c\ub294 \uc8fc\uc5b4\uc9c4 \ub3d9\uc804\uc758 \uc885\ub958\ub97c \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud55c \ub4a4, \uac00\uc7a5 \ud070 \ub3d9\uc804\ubd80\ud130 \uac00\ub2a5\ud55c \ub9cc\ud07c \uae08\uc561\uc5d0\uc11c \ucc28\uac10\ud558\uc5ec \ub3d9\uc804 \uac1c\uc218\ub97c \uc138\ub294 \ubc29\uc2dd\uc73c\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud569\ub2c8\ub2e4.<\/p>\n<\/section>\n \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n log n)\uc785\ub2c8\ub2e4. (n\uc740 \ub3d9\uc804\uc758 \uc885\ub958 \uac1c\uc218) \uc774 \ubb38\uc81c\ub294 \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc758 \uc804\ud615\uc801\uc778 \uc608\uc2dc\ub85c, \ub3d9\uc804\uc758 \uc885\ub958\uac00 \ub2e8\uc870 \uc99d\uac00\ud558\uac70\ub098, \ud2b9\uc815\ud55c \uaddc\uce59\uc131\uc774 \uc788\uc744 \uacbd\uc6b0 \ucd5c\uc801\uc758 \ud574\ub97c \ubcf4\uc7a5\ud569\ub2c8\ub2e4.<\/p>\n \ud558\uc9c0\ub9cc, \ubaa8\ub4e0 \uc0c1\ud669\uc5d0\uc11c \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc774 \ucd5c\uc801\uc758 \ud574\ub97c \ubcf4\uc7a5\ud558\uc9c0\ub294 \uc54a\uc73c\ubbc0\ub85c \uc57d\uac04\uc758 \uc8fc\uc758\uac00 \ud544\uc694\ud569\ub2c8\ub2e4. \ud2b9\uc9d5\uc801\uc778 \uc608\ub85c, \ub3d9\uc804\uc758 \uc885\ub958\uac00 {1, 3, 4}\uc77c \ub54c\ub294 \ucd5c\uc801\uc758 \ud574\ub97c \ucc3e\uc744 \uc218 \uc788\uc9c0\ub9cc, {1, 3, 4, 6} \uac19\uc774 \ub3d9\uc804\uc758 \uc885\ub958\uac00 \ucd94\uac00\ub418\uba74 \uacb0\uacfc\uac00 \ub2ec\ub77c\uc9c8 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n\ubb38\uc81c: \ub3d9\uc804 \uac70\uc2a4\ub984\ub3c8<\/h2>\n
\n
\ub3d9\uc804\uc758 \uc885\ub958: 1, 3, 4\n\uae08\uc561: 6\n<\/pre>\n
2 (3 + 3)\n<\/pre>\n<\/section>\n
\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
1. \ubb38\uc81c \ubd84\uc11d<\/h3>\n
2. \uc811\uadfc \ubc29\ubc95<\/h3>\n
\n
3. \uc54c\uace0\ub9ac\uc998 \uad6c\ud604 (Swift)<\/h3>\n
\nfunc minCoins(coins: [Int], amount: Int) -> Int {\n var remainingAmount = amount\n var coinCount = 0\n var sortedCoins = coins.sorted(by: { $0 > $1 }) \/\/ \ub0b4\ub9bc\ucc28\uc21c \uc815\ub82c\n \n for coin in sortedCoins {\n while remainingAmount >= coin {\n remainingAmount -= coin\n coinCount += 1\n }\n }\n return remainingAmount == 0 ? coinCount : -1 \/\/ \uc815\ud655\ud788 \uac70\uc2ac\ub7ec \uc8fc\uc9c0 \ubabb\ud560 \uacbd\uc6b0 -1 \ubc18\ud658\n}\n\n\/\/ \uc0ac\uc6a9 \uc608\uc2dc\nlet coins = [1, 3, 4]\nlet amount = 6\nlet result = minCoins(coins: coins, amount: amount)\nprint(\"\ucd5c\uc18c \ub3d9\uc804 \uac1c\uc218: \\(result)\")\n <\/code><\/pre>\n\uacb0\uacfc \ubd84\uc11d<\/h2>\n