\n \uc8fc\uc5b4\uc9c4 n\uac1c\uc758 \uc870\uc57d\ub3cc \uc911\uc5d0\uc11c m\uac1c\uc758 \uc870\uc57d\ub3cc\uc744 \uaebc\ub0b4\ub824\uace0 \ud560 \ub54c, \uc5b4\ub5a4 \uc870\uc57d\ub3cc\uc744 \uaebc\ub0b4\ub294 \uac83\uc774 \uac00\uc7a5 \uc88b\uc740 \uc120\ud0dd\uc778\uc9c0 \uc54c\uc544\ubcf4\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.
\n \uc774 \ubb38\uc81c\ub294 \ud0d0\uc695 \uc54c\uace0\ub9ac\uc998(Greedy Algorithm)\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc785\ub825\uc73c\ub85c\ub294 \uac01 \uc870\uc57d\ub3cc\uc758 \ubb34\uac8c\uac00 \uc8fc\uc5b4\uc9c0\uba70,
\n \uaebc\ub0bc \uc870\uc57d\ub3cc\ub4e4\uc758 \ucd1d \ubb34\uac8c\uac00 \ucd5c\ub300 K\uac00 \ub418\ub3c4\ub85d \ud574\uc57c \ud569\ub2c8\ub2e4.\n<\/p>\n
\n\uc785\ub825:<\/strong> \n\uc785\ub825 \uc608\uc2dc:<\/strong> \n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \uc6b0\uc120 \uc8fc\uc5b4\uc9c4 \uc870\uc57d\ub3cc\uc758 \ubb34\uac8c\ub97c \uc815\ub82c\ud55c \ud6c4, \uac00\uc7a5 \ubb34\uac70\uc6b4 \uc870\uc57d\ub3cc\ubd80\ud130 m\uac1c\ub97c \uc120\ud0dd\ud558\ub294 \uacfc\uc815\uc744 \uac70\uccd0\uc57c \ud569\ub2c8\ub2e4. \n \uc774\uc81c \uc704\uc758 \uc54c\uace0\ub9ac\uc998\uc744 \ubc14\ud0d5\uc73c\ub85c C++ \ucf54\ub4dc\ub97c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n \n \uc704\uc758 C++ \ucf54\ub4dc\ub294 \uc8fc\uc5b4\uc9c4 \uc870\uc57d\ub3cc\uc758 \uac1c\uc218\uc640 \uc120\ud0dd\ud574\uc57c \ud558\ub294 \uc870\uc57d\ub3cc\uc758 \uac1c\uc218\ub97c \uc785\ub825\ubc1b\uace0, \uac01 \uc870\uc57d\ub3cc\uc758 \ubb34\uac8c\ub97c \ubc30\uc5f4\uc5d0 \uc800\uc7a5\ud569\ub2c8\ub2e4. \n \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 \uc870\uc57d\ub3cc\uc758 \uac1c\uc218\ub97c n\uc774\ub77c\uace0 \ud560 \ub54c, O(n log n)\uc785\ub2c8\ub2e4. \uc815\ub82c \uacfc\uc815\uc774 \uac00\uc7a5 \ud070 \ube44\uc911\uc744 \ucc28\uc9c0\ud569\ub2c8\ub2e4. \n \uc774 \ubb38\uc81c\ub294 \ud0d0\uc695 \uc54c\uace0\ub9ac\uc998\uc758 \uae30\ucd08\ub97c \ubc30\uc6b0\uae30\uc5d0 \uc801\ud569\ud55c \uc5f0\uc2b5 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc870\uc57d\ub3cc\uc744 \uaebc\ub0b4\ub294 \ubb38\uc81c\ub97c \ud1b5\ud574 <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n – \uccab \ubc88\uc9f8 \uc904 : \uc870\uc57d\ub3cc\uc758 \uac1c\uc218 n (1 \u2264 n \u2264 100)
\n – \ub450 \ubc88\uc9f8 \uc904 : \uaebc\ub0b4\uc57c \ud560 \uc870\uc57d\ub3cc\uc758 \uac1c\uc218 m (1 \u2264 m \u2264 n)
\n – \uc138 \ubc88\uc9f8 \uc904 : \uc870\uc57d\ub3cc\uc758 \uac1c\uc218 n\uac1c\uc5d0 \ub300\ud55c \ubb34\uac8c (1 \u2264 weight \u2264 1000)
\n\ucd9c\ub825:<\/strong>
\n – \uaebc\ub0b8 \uc870\uc57d\ub3cc\ub4e4\uc758 \ubb34\uac8c\uc758 \ucd1d\ud569\uc774 \ucd5c\ub300 K\uac00 \ub418\ub3c4\ub85d \ud560 \ub54c, \uadf8 \ucd1d\ud569\uc744 \uad6c\ud558\ub77c.\n<\/p>\n3. \uc608\uc2dc<\/h2>\n
\n 5
\n 3
\n 1 2 3 4 5
\n\ucd9c\ub825 \uc608\uc2dc:<\/strong>
\n 12 (3 + 4 + 5)\n<\/p>\n4. \uc54c\uace0\ub9ac\uc998 \uc124\uacc4<\/h2>\n
\n \uc774\ub54c, \uc120\ud0dd\ub41c \uc870\uc57d\ub3cc\uc758 \ucd1d \ubb34\uac8c\ub97c \uacc4\uc0b0\ud558\uc5ec \uacb0\uacfc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998\uc758 \ub2e8\uacc4\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4.\n<\/p>\n\n
5. \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\n#include <iostream>\n#include <vector>\n#include <algorithm>\n\nint main() {\n int n, m;\n std::cout << \"\uc870\uc57d\ub3cc\uc758 \uac1c\uc218\ub97c \uc785\ub825\ud558\uc138\uc694: \";\n std::cin >> n;\n std::cout << \"\uaebc\ub0b4\uc57c \ud560 \uc870\uc57d\ub3cc\uc758 \uac1c\uc218\ub97c \uc785\ub825\ud558\uc138\uc694: \";\n std::cin >> m;\n\n std::vector<int> weights(n);\n std::cout << \"\uc870\uc57d\ub3cc\uc758 \ubb34\uac8c\ub97c \uc785\ub825\ud558\uc138\uc694 (\ub744\uc5b4\uc4f0\uae30\ub85c \uad6c\ubd84): \";\n for (int i = 0; i < n; ++i) {\n std::cin >> weights[i];\n }\n\n \/\/ \uc870\uc57d\ub3cc \ubb34\uac8c \uc815\ub82c\n std::sort(weights.begin(), weights.end());\n\n \/\/ \uac00\uc7a5 \ubb34\uac70\uc6b4 m\uac1c \uc870\uc57d\ub3cc \uc120\ud0dd\n int total_weight = 0;\n for (int i = n - m; i < n; ++i) {\n total_weight += weights[i];\n }\n\n std::cout << \"\uc120\ud0dd\ub41c \uc870\uc57d\ub3cc\uc758 \ucd1d \ubb34\uac8c: \" << total_weight << std::endl;\n\n return 0;\n}\n<\/code><\/pre>\n6. \ucf54\ub4dc \uc124\uba85<\/h2>\n
\n \uadf8\ub7f0 \ub2e4\uc74c, STL\uc758 sort<\/code> \uae30\ub2a5\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb34\uac8c\ub97c \uc815\ub82c\ud569\ub2c8\ub2e4. \uc815\ub82c\ub41c \ubc30\uc5f4\uc5d0\uc11c \uac00\uc7a5 \ubb34\uac70\uc6b4 m\uac1c\ub97c \uc120\ud0dd\ud558\uc5ec \ucd1d \ubb34\uac8c\ub97c \uacc4\uc0b0\ud558\uace0 \ucd9c\ub825\ud569\ub2c8\ub2e4.\n<\/p>\n7. \uc54c\uace0\ub9ac\uc998 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\n \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n)\uc774\uba70, \uc774\ub294 \uc785\ub825\uc73c\ub85c \ubc1b\uc740 \uc870\uc57d\ub3cc\uc758 \ubb34\uac8c\ub97c \uc800\uc7a5\ud558\uae30 \uc704\ud574 \ud544\uc694\ud55c \uba54\ubaa8\ub9ac\uc785\ub2c8\ub2e4.\n<\/p>\n8. \ubb38\uc81c \ud574\uacb0 \ud6c4\uae30<\/h2>\n
\n \ucd5c\uc801\ud654\ub41c \uc120\ud0dd\uc744 \ud560 \uc218 \uc788\ub294 \ubc29\ubc95\uc744 \uc775\ud790 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc2e4\uc81c \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c\ub3c4 \uc720\uc0ac\ud55c \ud615\ud0dc\uc758 \ubb38\uc81c\uac00 \uc790\uc8fc \ucd9c\uc81c\ub418\ubbc0\ub85c
\n \ubc18\ubcf5\uc801\uc778 \uc5f0\uc2b5\uc774 \ud544\uc694\ud569\ub2c8\ub2e4. \uc55e\uc73c\ub85c \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uba74\uc11c \ub354 \ub9ce\uc740 \uacbd\ud5d8\uc744 \uc313\uc544\uac00\uc2dc\uae38 \ubc14\ub78d\ub2c8\ub2e4.\n<\/p>\n