\n “\ubd80\ub140\ud68c\uc7a5\uc774 \ub420 \ud14c\uc57c” \ubb38\uc81c\ub294 \uc544\ud30c\ud2b8\uc758 \uce35\uacfc \ud638\uc218\uc5d0 \ub530\ub77c \uc0ac\ub78c\uc758 \uc218\ub97c \uacc4\uc0b0\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.
\n \uc8fc\uc5b4\uc9c4 \uce35\uc758 \uc778\ub371\uc2a4\uc640 \ud638\uc218\uc758 \uc778\ub371\uc2a4\ub97c \ud1b5\ud574 \uba87 \uba85\uc774 \uac70\uc8fc\ud558\ub294\uc9c0\ub97c \ud30c\uc545\ud574\uc57c \ud569\ub2c8\ub2e4.
\n \uc774 \ubb38\uc81c\uc758 \ud575\uc2ec\uc740 \ud53c\ub77c\ubbf8\ub4dc \uad6c\uc870\ub97c \ud65c\uc6a9\ud558\uc5ec \uac01 \uce35\uc5d0\uc11c\uc758 \uac70\uc8fc\uc790 \uc218\ub97c \uacc4\uc0b0\ud558\ub294 \uac83\uc785\ub2c8\ub2e4.\n<\/p>\n
\n \uc5b4\ub290 \uc544\ud30c\ud2b8\uc5d0 \uac70\uc8fc\ud558\ub294 \uc0ac\ub78c\uc758 \uc218\ub97c \uc815\uc758\ud558\ub294 \uaddc\uce59\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4.
\n 0\uce35(i=0)\uc758 \uacbd\uc6b0, i\ud638\ub294 \ud56d\uc0c1 1\uba85\uc785\ub2c8\ub2e4.
\n 1\uce35(i=1)\uc5d0\uc11c\ub294 i\ud638\uac00 1\uba85\uc5d0\uc11c \uc2dc\uc791\ud574, \uc704\uce35\uc758 \ubaa8\ub4e0 \ud638\uc218\uc5d0 \ud574\ub2f9\ud558\ub294 \uc0ac\ub78c\uc758 \uc218\ub97c \ud569\uc0b0\ud558\uc5ec \ub098\ud0c0\ub0a9\ub2c8\ub2e4.\n<\/p>\n
\n \uc989, f(n, k)\ub294 n\uce35 k\ud638\uc758 \uc0ac\ub78c \uc218\ub97c \ub098\ud0c0\ub0b4\uba74, \ub2e4\uc74c\uacfc \uac19\uc740 \uc7ac\uadc0 \ubc29\uc815\uc2dd\uc744 \uc138\uc6b8 \uc218 \uc788\uc2b5\ub2c8\ub2e4:\n<\/p>\n
f(n, k) = f(n-1, 1) + f(n-1, 2) + ... + f(n-1, k)<\/code><\/pre>\n\n \uc774 \uaddc\uce59\uc744 \ubc14\ud0d5\uc73c\ub85c, n\uce35 k\ud638\uc5d0 \uac70\uc8fc\ud558\ub294 \uc0ac\ub78c \uc218\ub294 (n-1)\uce35 1\ud638\ubd80\ud130 k\ud638\uae4c\uc9c0\uc758 \ud569\uc785\ub2c8\ub2e4.\n<\/p>\n
\ubb38\uc81c \ud480\uc774 \uc811\uadfc\ubc95<\/h2>\n
\n 1. **\uae30\ubcf8 \uc7ac\uadc0 \ud568\uc218 \uad6c\ud604**: \ubb38\uc81c\ub97c \ub2e8\uc21c\ud558\uac8c \ud480\uae30 \uc704\ud574, \uc7ac\uadc0\uc801\uc73c\ub85c \ub9ce\uc740 \ud638\ucd9c\uc774 \ubc1c\uc0dd\ud558\ub294 \ubc29\ubc95\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n 2. **\ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \ud65c\uc6a9**: \uc7ac\uadc0\uc801\uc778 \uc811\uadfc \ubc29\uc2dd\uc740 \ub3d9\uc77c\ud55c \uac12\uc744 \uc5ec\ub7ec \ubc88 \ud638\ucd9c\ud560 \uc218 \uc788\uc5b4 \ube44\ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.
\n \uc138\ubd80\uc801\uc778 \uacb0\uacfc\ub97c \uc800\uc7a5\ud558\ub294 \uba54\ubaa8\uc774\uc81c\uc774\uc158(\ub610\ub294 \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d)\uc744 \ud1b5\ud574 \uc131\ub2a5\uc744 \uac1c\uc120\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n<\/p>\n
\n \uc774 \ubb38\uc81c\ub294 \uce35\uacfc \ud638\uc218\ub97c \uae30\ubc18\uc73c\ub85c \ud14c\uc774\ube14\uc744 \uc0dd\uc131\ud558\uc5ec, \ubaa8\ub4e0 \uacc4\uc0b0\ub41c \uac12\ub4e4\uc744 \uc800\uc7a5\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n<\/p>\n
C++ \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\n \uc544\ub798\uc758 \ucf54\ub4dc\ub294 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \uc0ac\uc6a9\ud558\uc5ec, \uc8fc\uc5b4\uc9c4 \uce35\uacfc \ud638\uc218\uc758 \uc0ac\ub78c \uc218\ub97c \uacc4\uc0b0\ud558\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4:\n<\/p>\n
\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nint main() {\n int T; \/\/ \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4 \uc218\n cin >> T;\n \n while (T--) {\n int k, n; \/\/ k: \ud638\uc218, n: \uce35\n cin >> k >> n;\n \n vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));\n\n \/\/ 0\uce35 \ucd08\uae30\ud654\n for (int i = 1; i <= k; ++i) {\n dp[0][i] = 1; \/\/ 0\uce35 i\ud638\uc5d0\ub294 \ud56d\uc0c1 1\uba85\n }\n\n \/\/ DP \ud14c\uc774\ube14 \uad6c\uc131\n for (int i = 1; i <= n; ++i) {\n for (int j = 1; j <= k; ++j) {\n dp[i][j] = dp[i - 1][j] + dp[i][j - 1];\n }\n }\n\n \/\/ \uacb0\uacfc \ucd9c\ub825\n cout << dp[n][k] << endl;\n }\n \n return 0;\n}\n<\/code><\/pre>\n\uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\n \uc704\uc758 \uad6c\ud604 \ubc29\uc2dd\uc740 T\uac1c\uc758 \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\uc5d0 \ub300\ud574 \uac01\uac01 n\uce35 k\ud638\uae4c\uc9c0 \uacc4\uc0b0\ud558\ubbc0\ub85c, \ucd5c\uc545\uc758 \uacbd\uc6b0 O(n * k)<\/code>\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9d1\ub2c8\ub2e4.
\n \uad6c\ud604\ub41c \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \ubc29\uc2dd\uc740 \uacf5\uac04 \ubcf5\uc7a1\ub3c4 \ub610\ud55c O(n * k)<\/code>\ub97c \uc694\uad6c\ud569\ub2c8\ub2e4.\n<\/p>\n\uacb0\ub860<\/h2>\n
\n “\ubd80\ub140\ud68c\uc7a5\uc774 \ub420 \ud14c\uc57c” \ubb38\uc81c\ub294 \ubb38\uc81c\uc758 \uaddc\uce59\uc744 \uc774\ud574\ud558\uace0, \uc801\uc808\ud55c \uc54c\uace0\ub9ac\uc998\uc744 \uc120\ud0dd\ud574 \uad6c\ud604\ud568\uc73c\ub85c\uc368 \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n C++\uc758 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \uae30\ubc95\uc744 \ud1b5\ud574 \uc131\ub2a5\uc744 \uadf9\ub300\ud654\ud560 \uc218 \uc788\uc73c\uba70, \uc774\ub7ec\ud55c \uc811\uadfc\uc740 \ub2e4\uc591\ud55c \uc720\uc0ac\ud55c \ubb38\uc81c\ub97c \ud480 \ub54c\uc5d0\ub3c4 \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n<\/p>\n
\ucd94\uac00 \ubb38\uc81c \ubc0f \uc5f0\uc2b5<\/h2>\n
\n \ubb38\uc81c\ub97c \ub354 \uae4a\uc774 \uc774\ud574\ud558\uace0 \uc2f6\ub2e4\uba74, \ub2e4\uc74c\uacfc \uac19\uc740 \ubcc0\ud615 \ubb38\uc81c\ub97c \uc2dc\ub3c4\ud574\ubcf4\ub294 \uac83\uc744 \ucd94\ucc9c\ud569\ub2c8\ub2e4:\n<\/p>\n