\uc8fc\uc5b4\uc9c4 \uc815\uc218 \ubc30\uc5f4\uc774 \uc788\uc744 \ub54c, \uc774\ub97c \ub450 \uac1c\uc758 \ubd80\ubd84\uc9d1\ud569\uc73c\ub85c \ub098\ub204\uc5b4 \uac01\uac01\uc758 \ud569\uc774 \ub3d9\uc77c\ud558\uac8c \ub9cc\ub4e4 \uc218 \uc788\ub294\uc9c0 \uc5ec\ubd80\ub97c \ud655\uc778\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc2dc\uc624.<\/p>\n
\uc774 \ubb38\uc81c\ub294 ‘\ubd80\ubd84 \uc9d1\ud569 \ud569 \ubb38\uc81c'(Subset Sum Problem)\uc5d0 \ud574\ub2f9\ud569\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming)\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\ubd80\ubd84\uc9d1\ud569\uc744 \ub098\ub20c \uc218 \uc788\uc73c\uba74 “YES”\ub97c, \ubd88\uac00\ub2a5\ud558\uba74 “NO”\ub97c \ucd9c\ub825\ud55c\ub2e4.<\/p>\n
\n 4\n 1 5 11 5\n <\/pre>\n\uc608\uc81c \ucd9c\ub825<\/h2>\n
\n YES\n <\/pre>\n\ubb38\uc81c \ud574\uacb0 \uc811\uadfc\ubc95<\/h2>\n
\uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \uba3c\uc800 \ub2e4\uc74c \ub2e8\uacc4\ub97c \ub530\ub77c\uc57c \ud569\ub2c8\ub2e4:<\/p>\n
\n
- \uc785\ub825 \ubc30\uc5f4\uc758 \ud569\uc744 \uacc4\uc0b0\ud569\ub2c8\ub2e4.<\/li>\n
- \ud569\uc774 \ud640\uc218\uc778 \uacbd\uc6b0, \ub450 \ubd80\ubd84\uc9d1\ud569\uc758 \ud569\uc774 \uac19\uc744 \uc218 \uc5c6\uc73c\ubbc0\ub85c “NO”\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4.<\/li>\n
- \ud569\uc774 \uc9dd\uc218\uc778 \uacbd\uc6b0, \ubaa9\ud45c\uac12\uc744 \ud569\uc758 \uc808\ubc18\uc73c\ub85c \uc124\uc815\ud558\uace0 \uc774\ub97c \ub2ec\uc131\ud560 \uc218 \uc788\ub294\uc9c0 \ud310\ub2e8\ud558\uae30 \uc704\ud574 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/li>\n
- \uc0c1\ud0dc \ud14c\uc774\ube14\uc744 \uc124\uc815\ud558\uace0, \uac01 \uc22b\uc790\uac00 \ubaa9\ud45c\uac12\uc744 \ub9cc\ub4dc\ub294 \ub370 \uc0ac\uc6a9\ub420 \uc218 \uc788\ub294\uc9c0 \ud655\uc778\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
C++ \ucf54\ub4dc<\/h2>\n
\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nbool canPartition(vector<int>& arr) {\n int sum = 0;\n for (int num : arr) sum += num;\n if (sum % 2 != 0) return false;\n\n int target = sum \/ 2;\n vector<bool> dp(target + 1, false);\n dp[0] = true;\n\n for (int num : arr) {\n for (int j = target; j >= num; j--) {\n dp[j] = dp[j] || dp[j - num];\n }\n }\n\n return dp[target];\n}\n\nint main() {\n int N;\n cin >> N;\n vector<int> arr(N);\n for (int i = 0; i < N; i++) {\n cin >> arr[i];\n }\n \n cout << (canPartition(arr) ? \"YES\" : \"NO\") << endl;\n return 0;\n}\n <\/pre>\n\ucf54\ub4dc \uc124\uba85<\/h2>\n
\uc704\uc758 \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ubc29\uc2dd\uc73c\ub85c \uc791\ub3d9\ud569\ub2c8\ub2e4:<\/p>\n
\n
- \uba3c\uc800 \uc22b\uc790 \ubc30\uc5f4\uc758 \ucd1d\ud569\uc744 \uacc4\uc0b0\ud569\ub2c8\ub2e4.<\/li>\n
- \ud569\uc774 \ud640\uc218\uc778\uc9c0 \ud655\uc778\ud569\ub2c8\ub2e4. \ud640\uc218\ub77c\uba74 “NO”\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4.<\/li>\n
- \ud569\uc774 \uc9dd\uc218\uc774\uba74, \ubaa9\ud45c\uac12\uc744 \ud569\uc758 \uc808\ubc18\uc73c\ub85c \uc124\uc815\ud558\uace0 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \ubc30\uc5f4\uc744 \ucd08\uae30\ud654\ud569\ub2c8\ub2e4.<\/li>\n
- \uac01 \uc22b\uc790\ub97c \ubc18\ubcf5\ud558\uba74\uc11c \ubaa9\ud45c\uac12\uc5d0 \uc774\ub97c \ub9cc\ub4e4 \uc218 \uc788\ub294\uc9c0 \ud655\uc778\ud569\ub2c8\ub2e4.<\/li>\n
- \uacb0\uacfc\uc801\uc73c\ub85c \ubaa9\ud45c\uac12\uc744 \ub9cc\ub4e4 \uc218 \uc788\uc73c\uba74 “YES”, \uadf8\ub807\uc9c0 \uc54a\uc73c\uba74 “NO”\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4<\/h2>\n
\uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N * target)\uc785\ub2c8\ub2e4. \uc5ec\uae30\uc11c N\uc740 \uc785\ub825 \uc22b\uc790\uc758 \uac1c\uc218\uc774\uace0, target\uc740 \uc785\ub825 \ubc30\uc5f4\uc758 \ucd1d\ud569\uc758 \uc808\ubc18\uc785\ub2c8\ub2e4. \uc774\ub85c \uc778\ud574 \uc11c\ub85c \ub2e4\ub978 \ubd80\ubd84\uc9d1\ud569\uc744 \uc0dd\uc131\ud558\uae30 \uc704\ud574 \uc0ac\uc6a9\ub420 \uc218 \uc788\ub294 \uc5f0\uc0b0\uc758 \uc218\uac00 \uacb0\uc815\ub429\ub2c8\ub2e4.<\/p>\n
\ub9c8\ubb34\ub9ac<\/h2>\n
\uc5ec\uae30\uae4c\uc9c0\uac00 \ubd80\ubd84 \uc9d1\ud569 \ud569 \ubb38\uc81c\uc758 \ucf54\ub4dc\uc640 \uc124\uba85\uc785\ub2c8\ub2e4. \uc774\uc640 \uac19\uc740 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub294 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ub294 \uc720\ud615\uc774\ubbc0\ub85c, \uc790\uc8fc \uc5f0\uc2b5\ud574 \ubcf4\ub294 \uac83\uc774 \uc88b\uc2b5\ub2c8\ub2e4. \ub2e4\uc74c \uac15\uc88c\uc5d0\uc11c\ub294 \uc880 \ub354 \ubcf5\uc7a1\ud55c \ubb38\uc81c\ub4e4\uacfc \uadf8 \ud574\uacb0 \ubc29\ubc95\uc5d0 \ub300\ud574 \ub2e4\ub8e8\uc5b4 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\uc9c8\ubb38\uacfc \ud53c\ub4dc\ubc31<\/h2>\n
\uc791\uc131\ud55c \ucf54\ub4dc\ub098 \uc774\ud574\uac00 \uc5b4\ub824\uc6b4 \ubd80\ubd84\uc5d0 \ub300\ud574 \uad81\uae08\ud55c \uc810\uc774 \uc788\uc73c\uba74 \uc5b8\uc81c\ub4e0\uc9c0 \ub313\uae00\ub85c \ub0a8\uaca8\uc8fc\uc138\uc694!<\/p>\n<\/div>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"