1. \ubb38\uc81c \uc124\uba85<\/h2>\n
\n \uacc4\ub2e8 \uc218\ub294 \ud2b9\uc815 \uc870\uac74\uc5d0 \ub9de\ub294 \uc218\ub97c \uc138\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. N (1 \u2264 N \u2264 100), \uc8fc\uc5b4\uc9c4 \uc790\uc5f0\uc218\uc778 N\uc740 \uacc4\ub2e8 \uc218\uc758 \uc790\ub9ac \uc218\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4.<\/p>\n N\uc790\ub9ac \uacc4\ub2e8 \uc218\uc758 \uac1c\uc218\ub97c 1,000,000,000\uc73c\ub85c \ub098\ub208 \ub098\uba38\uc9c0\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n<\/section>\n \n \uacc4\ub2e8 \uc218\ub97c \uc138\uae30 \uc704\ud574\uc11c\ub294 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming) \ubc29\uc2dd\uc744 \uc120\ud0dd\ud574\uc57c \ud569\ub2c8\ub2e4. \n \uc774\ub97c \ubc14\ud0d5\uc73c\ub85c DP \ud14c\uc774\ube14\uc744 \uad6c\uc131\ud558\uace0, \uac01 \uc790\ub9ac\uc218\uc5d0 \ub530\ub978 \uacc4\ub2e8 \uc218\ub97c \uae30\ub85d\ud574 \ub098\uac00\uba74\uc11c \n \uc774\uc81c \ubcf8\uaca9\uc801\uc73c\ub85c C#\uc73c\ub85c \uacc4\ub2e8 \uc218\ub97c \uad6c\ud558\ub294 \ucf54\ub4dc\ub97c \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \n \uc704\uc758 \ucf54\ub4dc\ub97c \ub2e8\uacc4\ubcc4\ub85c \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4. \n \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N)\uc785\ub2c8\ub2e4. \n \uc704\uc758 \uc608\uc81c\uc5d0\uc11c 3\uc790\ub9ac \uacc4\ub2e8 \uc218\ub294 32\uac1c\uac00 \uc874\uc7ac\ud569\ub2c8\ub2e4. \n \uc774 \uac15\uc88c\uc5d0\uc11c\ub294 \uacc4\ub2e8 \uc218\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\ub97c \ud1b5\ud574 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc758 \uae30\ucd08\uc801\uc778 <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n \uc8fc\uc5b4\uc9c4 \uc218 N\uc774 \uc788\uc744 \ub54c, N \uc790\ub9ac\uc758 \uacc4\ub2e8 \uc218\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uaca0\uc2b5\ub2c8\ub2e4.
\n \uacc4\ub2e8 \uc218\ub780 \uac01 \uc790\ub9ac\uc758 \uc218\uac00 \uadf8 \ub2e4\uc74c \uc790\ub9ac \uc218\ubcf4\ub2e4 1\ub9cc\ud07c \ud06c\uac70\ub098 \uc791\uc544\uc57c \ud558\ub294 \uc218\uc785\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, 1234, 3210\uc740 \uacc4\ub2e8 \uc218\uc785\ub2c8\ub2e4.
\n \uadf8\ub7ec\ub098 1123, 2222\ub294 \uacc4\ub2e8 \uc218\uac00 \uc544\ub2d9\ub2c8\ub2e4.
\n \uc774 \ubb38\uc81c\ub97c \ud1b5\ud574 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc758 \uae30\ubcf8 \uc544\uc774\ub514\uc5b4\uc640 \uad6c\ud604 \ubc29\ubc95\uc744 \uc774\ud574\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n<\/section>\n2. \uc785\ub825 & \ucd9c\ub825 \ud615\uc2dd<\/h2>\n
\uc785\ub825<\/h3>\n
\ucd9c\ub825<\/h3>\n
3. \ubb38\uc81c \uc811\uadfc \ubc29\ubc95<\/h2>\n
\n \ubb38\uc81c\ub97c \ud480\uae30 \uc704\ud574 \ub2e4\uc74c\uacfc \uac19\uc740 \ubc29\ubc95\uc73c\ub85c \uc811\uadfc\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n N\uc790\ub9ac \uacc4\ub2e8 \uc218\ub97c \uad6c\ud558\uae30 \uc704\ud574, (N-1)\uc790\ub9ac \uacc4\ub2e8 \uc218\ub97c \uc774\uc6a9\ud558\uc5ec \uac12\uc744 \uacc4\uc0b0\ud569\ub2c8\ub2e4.
\n \ub2e4\uc74c\uacfc \uac19\uc740 \uaddc\uce59\uc744 \ucc3e\uc544\ub0bc \uc218 \uc788\uc2b5\ub2c8\ub2e4:\n <\/p>\n\n
\n \ucd5c\uc885\uc801\uc73c\ub85c N\uc790\ub9ac \uacc4\ub2e8 \uc218\ub97c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n DP \ubc30\uc5f4\uc744 \ucd08\uae30\ud654\ud558\uace0, \uc810\ucc28\uc801\uc73c\ub85c \ucc44\uc6cc\ub098\uac00\ub294 \ubc29\uc2dd\uc73c\ub85c \uc811\uadfc\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n4. C# \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\n \uc544\ub798\ub294 \ubb38\uc81c \ud574\uacb0\uc744 \uc704\ud55c C# \ucf54\ub4dc\uc785\ub2c8\ub2e4.\n <\/p>\n\nusing System;\n\nclass Program\n{\n static void Main()\n {\n int N = int.Parse(Console.ReadLine());\n long[,] dp = new long[N + 1, 10];\n\n \/\/ 1\uc790\ub9ac \uacc4\ub2e8 \uc218 \ucd08\uae30\ud654 (1~9)\n for (int i = 1; i <= 9; i++)\n {\n dp[1, i] = 1;\n }\n\n \/\/ DP\ub97c \ud65c\uc6a9\ud558\uc5ec N\uc790\ub9ac \uacc4\ub2e8\uc218 \uad6c\ud558\uae30\n for (int i = 2; i <= N; i++)\n {\n for (int j = 0; j <= 9; j++)\n {\n if (j == 0)\n {\n dp[i, j] = dp[i - 1, j + 1] % 1000000000; \/\/ 0 -> 1\n }\n else if (j == 9)\n {\n dp[i, j] = dp[i - 1, j - 1] % 1000000000; \/\/ 9 -> 8\n }\n else\n {\n dp[i, j] = (dp[i - 1, j - 1] + dp[i - 1, j + 1]) % 1000000000; \/\/ j-1, j+1\n }\n }\n }\n\n \/\/ N\uc790\ub9ac \uacc4\ub2e8\uc218\uc758 \ucd1d\ud569 \uacc4\uc0b0\n long result = 0;\n for (int j = 0; j <= 9; j++)\n {\n result = (result + dp[N, j]) % 1000000000;\n }\n\n \/\/ \uacb0\uacfc \ucd9c\ub825\n Console.WriteLine(result);\n }\n}\n <\/code><\/pre>\n<\/section>\n5. \ucf54\ub4dc \uc124\uba85<\/h2>\n
\n 1. \uc6b0\uc120, \uc0ac\uc6a9\uc790\uc758 \uc785\ub825\uc73c\ub85c\ubd80\ud130 N\uc744 \uc77d\uc5b4\uc635\ub2c8\ub2e4.
\n 2. 2\ucc28\uc6d0 \ubc30\uc5f4 dp\ub97c \uc0dd\uc131\ud558\uc5ec dp[i, j]\ub294 i\uc790\ub9ac\uc758 \uacc4\ub2e8 \uc218 \uc911 j\ub85c \ub05d\ub098\ub294 \uc218\uc758 \uac1c\uc218\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4.
\n 3. 1\uc790\ub9ac \uc218\ub294 0~9 \uc911\uc5d0\uc11c 1~9\ub9cc \uc0ac\uc6a9 \uac00\ub2a5\ud558\ubbc0\ub85c \uc774\ub97c \ucd08\uae30\ud654\ud569\ub2c8\ub2e4.
\n 4. \uc774\ud6c4, 2\uc790\ub9ac\ubd80\ud130 N\uc790\ub9ac\uae4c\uc9c0 \uac01 \uc790\ub9ac\uc218\ub97c \uacc4\uc0b0\ud569\ub2c8\ub2e4.
\n 5. \uac01 \uc790\ub9ac\uc218\uc758 \uacc4\uc0b0\uc740 \uc704\uc5d0\uc11c \uc124\uba85\ud55c \uaddc\uce59\uc5d0 \ub530\ub77c \uc774\ub8e8\uc5b4\uc9d1\ub2c8\ub2e4.
\n 6. \ub9c8\uc9c0\ub9c9\uc73c\ub85c N\uc790\ub9ac\uc758 \uacc4\ub2e8\uc218\ub97c \ubaa8\ub450 \ud569\uc0b0\ud558\uc5ec \uacb0\uacfc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n6. \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\n N\uc774 100\uc77c \ub54c, 2\uc911 \ub8e8\ud504\ub97c \ud1b5\ud574\uc11c \uac01 \uc790\ub9ac\uc218\uc5d0 \ub300\ud55c \uac00\ub2a5\uc131\uc744 \ud655\uc778\ud558\ubbc0\ub85c
\n O(N) * O(10) = O(N)\uc5d0 \ud574\ub2f9\ud569\ub2c8\ub2e4.
\n \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N * 10)\uc774\uba70, \uc774\ub294 \uba54\ubaa8\ub9ac \uc0ac\uc6a9\ub7c9\uc774 \ube44\uad50\uc801 \uc801\ub2e4\ub294 \uac83\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n7. \uc608\uc81c<\/h2>\n
\uc785\ub825 \uc608\uc2dc<\/h3>\n
\n3\n <\/code><\/pre>\n\ucd9c\ub825 \uc608\uc2dc<\/h3>\n
\n32\n <\/code><\/pre>\n
\n \uc774\ub97c \ud1b5\ud574 \ubb38\uc81c\ub97c \uc774\ud574\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n<\/section>\n8. \uacb0\ub860<\/h2>\n
\n \uac1c\ub150\uc744 \uc775\ud614\uc2b5\ub2c8\ub2e4.
\n \uacc4\ub2e8 \uc218 \ubb38\uc81c\ub294 \uc54c\uace0\ub9ac\uc998 \uc2a4\ud0ac\uc744 \ud5a5\uc0c1\uc2dc\ud0a4\ub294 \ub370 \ub3c4\uc6c0\uc774 \ub418\ub294 \uc88b\uc740 \uc5f0\uc2b5 \ubb38\uc81c\uac00 \ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uba74\uc11c \ub354 \ub9ce\uc740 \uacbd\ud5d8\uc744 \uc313\uae38 \ubc14\ub78d\ub2c8\ub2e4.
\n \uc55e\uc73c\ub85c\ub3c4 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \ud480\uc774\uc5d0 \ub3c4\uc804\ud558\uc138\uc694!\n <\/p>\n<\/section>\n<\/article>\n