\ubb38\uc81c \uc124\uba85<\/h2>\n
\n \uacc4\ub2e8 \uc218\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uaddc\uce59\uc744 \ub530\ub985\ub2c8\ub2e4. n\uc790\ub9ac \uc218\uc774\uba70, \uac01 \uc790\ub9ac \uc22b\uc790\ub294 \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc99d\uac00\ud574\uc57c \ud569\ub2c8\ub2e4. \uc989, \uc778\uc811\ud55c \ub450 \uc790\ub9ac \uc218\uc758 \ucc28\uc774\ub294 \uc815\ud655\ud788 1\uc774\uc5b4\uc57c \ud569\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, 123, 234, 345\ub294 \ubaa8\ub450 \uacc4\ub2e8 \uc218\uc785\ub2c8\ub2e4.\n <\/p>\n
\ubb38\uc81c<\/h3>\n
\n N\uc774 \uc8fc\uc5b4\uc9c8 \ub54c, N\uc790\ub9ac \uacc4\ub2e8 \uc218\uc758 \uac1c\uc218\ub97c \uad6c\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc138\uc694.\n <\/p>\n
\uc785\ub825<\/h3>\n\n- \uccab \ubc88\uc9f8 \uc904\uc5d0 \uc790\uc5f0\uc218 N\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. (1 \u2264 N \u2264 100)<\/li>\n<\/ul>\n
\ucd9c\ub825<\/h3>\n\n- N\uc790\ub9ac \uacc4\ub2e8 \uc218\uc758 \uac1c\uc218\ub97c 10007\ub85c \ub098\ub208 \ub098\uba38\uc9c0\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\uc608\uc81c \uc785\ub825<\/h3>\n3<\/pre>\n\uc608\uc81c \ucd9c\ub825<\/h3>\n14<\/pre>\n\uc124\uba85<\/h3>\n
\n N\uc774 3\uc774\uba74, 3\uc790\ub9ac \uacc4\ub2e8 \uc218\ub294 123, 132, 210, 321, 234, 345, 456, 567, 678, 789 \ub4f1 \ucd1d 14\uac1c\uac00 \uc874\uc7ac\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n\n\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
\n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming)\uc758 \uae30\ubc95\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n \uacc4\ub2e8 \uc218\ub294 \uc774\uc804 N-1\uc790\ub9ac \uc218\ub97c \uae30\ubc18\uc73c\ub85c \ud55c N\uc790\ub9ac \uc218\uc758 \uc870\ud569\uc73c\ub85c \uc0dd\uac01\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. N-1\uc790\ub9ac \uc218\uc758 \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uc5d0 \ub530\ub77c N\uc790\ub9ac \uc218\uc758 \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uac00 \uacb0\uc815\ub418\ubbc0\ub85c, \uc774\ub97c \uace0\ub824\ud558\uc5ec DP \ubc30\uc5f4\uc744 \uc5c5\ub370\uc774\ud2b8\ud558\uba74 \ub429\ub2c8\ub2e4.\n <\/p>\n
\ud480\uc774 \uc811\uadfc \ubc29\uc2dd<\/h3>\n\n- \n\uc0c1\ud0dc \uc815\uc758<\/strong>: dp[n][last]\ub97c n\uc790\ub9ac \uacc4\ub2e8 \uc218 \uc911 \ub9c8\uc9c0\ub9c9 \uc790\ub9ac \uc218\uac00 last\uc778 \uacbd\uc6b0\uc758 \uac1c\uc218\ub85c \uc815\uc758\ud569\ub2c8\ub2e4. n\uc740 \uc790\ub9ac \uc218\ub97c \uc758\ubbf8\ud558\uba70, last\ub294 \ub9c8\uc9c0\ub9c9 \uc22b\uc790(0~9)\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4.\n <\/li>\n
- \n\ucd08\uae30 \uc0c1\ud0dc \uc124\uc815<\/strong>: 1\uc790\ub9ac \uc218\uc758 \uacbd\uc6b0(\uc989, N=1\uc77c \ub54c) \uac01 \uc22b\uc790(1~9)\ub294 \uac01\uae30 1\uac1c\uc758 \uacbd\uc6b0\uc758 \uc218\ub97c \uac00\uc9d1\ub2c8\ub2e4. \ub530\ub77c\uc11c dp[1][1] ~ dp[1][9]\ub294 1, dp[1][0]\ub294 0\uc785\ub2c8\ub2e4.\n <\/li>\n
- \n\uc0c1\ud0dc \uc804\uc774<\/strong>: n\uc790\ub9ac \uc218\ub294 n-1\uc790\ub9ac \uc218\uc5d0\uc11c \ub9cc\ub4e4\uc5b4\uc9d1\ub2c8\ub2e4. \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uac00 last\uc77c \ub54c, \ub9c8\uc9c0\ub9c9 \uc22b\uc790\ub294 last-1 \ub610\ub294 last+1\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ub97c \uc218\uc2dd\uc73c\ub85c \ud45c\ud604\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4. <\/p>\n
\n dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]\n <\/pre>\n \uc5ec\uae30\uc11c last\ub294 1\ubd80\ud130 8\uae4c\uc9c0\uc758 \ubc94\uc704\ub97c \uac00\uc9c8 \uc218 \uc788\uc2b5\ub2c8\ub2e4(0\uacfc 9\ub294 \uac01\uac01 \ud55c\ucabd\uc5d0 \ud55c\uc815\ub418\ubbc0\ub85c).\n <\/li>\n
- \n\uacb0\uacfc \uacc4\uc0b0<\/strong>: N\uc790\ub9ac \uc218\uc758 \uac1c\uc218\ub294 dp[N][0] + dp[N][1] + … + dp[N][9]\uc758 \ud569\uc785\ub2c8\ub2e4. \uadf8\ub7ec\ub098 \ubb38\uc81c\uc5d0\uc11c \uc694\uad6c\ud558\ub294 \uac83\uc740 10007\ub85c \ub098\ub208 \ub098\uba38\uc9c0\uc774\ubbc0\ub85c, \uacc4\uc0b0 \uacfc\uc815\uc5d0\uc11c \uc774 \uc5f0\uc0b0\uc744 \uc218\ud589\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/li>\n<\/ol>\n<\/section>\n
\n\uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h2>\n\n import java.util.Scanner;\n\n public class StairNumber {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int N = sc.nextInt();\n int MOD = 10007;\n\n \/\/ DP \ubc30\uc5f4 \ucd08\uae30\ud654\n int[][] dp = new int[N + 1][10];\n\n \/\/ 1\uc790\ub9ac \uc218 \ucd08\uae30\ud654\n for (int i = 1; i < 10; i++) {\n dp[1][i] = 1;\n }\n\n \/\/ DP \ud14c\uc774\ube14 \uad6c\uc131\n for (int n = 2; n <= N; n++) {\n for (int last = 0; last <= 9; last++) {\n if (last > 0) { \/\/ last\uac00 0\uc774 \uc544\ub2d0 \uacbd\uc6b0\n dp[n][last] += dp[n - 1][last - 1];\n }\n if (last < 9) { \/\/ last\uac00 9\uac00 \uc544\ub2d0 \uacbd\uc6b0\n dp[n][last] += dp[n - 1][last + 1];\n }\n dp[n][last] %= MOD; \/\/ MOD \uc5f0\uc0b0\n }\n }\n\n \/\/ \uacb0\uacfc \ud569\uc0b0\n int result = 0;\n for (int last = 0; last <= 9; last++) {\n result = (result + dp[N][last]) % MOD;\n }\n\n \/\/ \uacb0\uacfc \ucd9c\ub825\n System.out.println(result);\n sc.close();\n }\n }\n <\/pre>\n<\/section>\n\n\uc608\uc2dc<\/h2>\n\uc785\ub825<\/h3>\n3<\/pre>\n\ucd9c\ub825<\/h3>\n14<\/pre>\n\uc704\uc758 \ucf54\ub4dc\ub97c \uc2e4\ud589\ud558\uac8c \ub418\uba74, 3\uc790\ub9ac \uacc4\ub2e8 \uc218\uc758 \uac1c\uc218\ub97c \uc815\ud655\ud558\uac8c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\ucd94\uac00 \uc0ac\ud56d<\/h2>\n
\n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uace0 \ub09c \ud6c4, \ub2e4\uc591\ud55c \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\ub85c \uc54c\uace0\ub9ac\uc998\uc758 \uc815\ud655\uc131\uc744 \uac80\uc99d\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \ub610\ud55c \ucf54\ub4dc\ub97c \ucd5c\uc801\ud654\ud558\uac70\ub098 \ub2e4\uc591\ud55c \ubc29\ubc95\uc73c\ub85c \uc54c\uace0\ub9ac\uc998\uc744 \uc811\uadfc\ud558\uc5ec \uadf8 \uacb0\uacfc\ub97c \ube44\uad50\ud558\ub294 \uac83\ub3c4 \uc88b\uc740 \ubc29\ubc95\uc785\ub2c8\ub2e4.\n <\/p>\n
\n \ub9c8\uc9c0\ub9c9\uc73c\ub85c, \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d \ubb38\uc81c\ub294 \ub9ce\uc740 \uacbd\uc6b0 \uadf8\ub798\ud504 \uc774\ub860\uacfc\ub3c4 \uc5f0\uacb0\ub420 \uc218 \uc788\uc73c\ub2c8, \ud56d\uc0c1 \uc774\ub7ec\ud55c \uad00\uc810\uc744 \uac16\uace0 \ubb38\uc81c\ub97c \ud478\uc154\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n
<\/main><\/p>\n
\ucd9c\ub825<\/h3>\n\n- N\uc790\ub9ac \uacc4\ub2e8 \uc218\uc758 \uac1c\uc218\ub97c 10007\ub85c \ub098\ub208 \ub098\uba38\uc9c0\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\uc608\uc81c \uc785\ub825<\/h3>\n3<\/pre>\n\uc608\uc81c \ucd9c\ub825<\/h3>\n14<\/pre>\n\uc124\uba85<\/h3>\n
\n N\uc774 3\uc774\uba74, 3\uc790\ub9ac \uacc4\ub2e8 \uc218\ub294 123, 132, 210, 321, 234, 345, 456, 567, 678, 789 \ub4f1 \ucd1d 14\uac1c\uac00 \uc874\uc7ac\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n\n\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
\n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming)\uc758 \uae30\ubc95\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n \uacc4\ub2e8 \uc218\ub294 \uc774\uc804 N-1\uc790\ub9ac \uc218\ub97c \uae30\ubc18\uc73c\ub85c \ud55c N\uc790\ub9ac \uc218\uc758 \uc870\ud569\uc73c\ub85c \uc0dd\uac01\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. N-1\uc790\ub9ac \uc218\uc758 \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uc5d0 \ub530\ub77c N\uc790\ub9ac \uc218\uc758 \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uac00 \uacb0\uc815\ub418\ubbc0\ub85c, \uc774\ub97c \uace0\ub824\ud558\uc5ec DP \ubc30\uc5f4\uc744 \uc5c5\ub370\uc774\ud2b8\ud558\uba74 \ub429\ub2c8\ub2e4.\n <\/p>\n
\ud480\uc774 \uc811\uadfc \ubc29\uc2dd<\/h3>\n\n- \n\uc0c1\ud0dc \uc815\uc758<\/strong>: dp[n][last]\ub97c n\uc790\ub9ac \uacc4\ub2e8 \uc218 \uc911 \ub9c8\uc9c0\ub9c9 \uc790\ub9ac \uc218\uac00 last\uc778 \uacbd\uc6b0\uc758 \uac1c\uc218\ub85c \uc815\uc758\ud569\ub2c8\ub2e4. n\uc740 \uc790\ub9ac \uc218\ub97c \uc758\ubbf8\ud558\uba70, last\ub294 \ub9c8\uc9c0\ub9c9 \uc22b\uc790(0~9)\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4.\n <\/li>\n
- \n\ucd08\uae30 \uc0c1\ud0dc \uc124\uc815<\/strong>: 1\uc790\ub9ac \uc218\uc758 \uacbd\uc6b0(\uc989, N=1\uc77c \ub54c) \uac01 \uc22b\uc790(1~9)\ub294 \uac01\uae30 1\uac1c\uc758 \uacbd\uc6b0\uc758 \uc218\ub97c \uac00\uc9d1\ub2c8\ub2e4. \ub530\ub77c\uc11c dp[1][1] ~ dp[1][9]\ub294 1, dp[1][0]\ub294 0\uc785\ub2c8\ub2e4.\n <\/li>\n
- \n\uc0c1\ud0dc \uc804\uc774<\/strong>: n\uc790\ub9ac \uc218\ub294 n-1\uc790\ub9ac \uc218\uc5d0\uc11c \ub9cc\ub4e4\uc5b4\uc9d1\ub2c8\ub2e4. \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uac00 last\uc77c \ub54c, \ub9c8\uc9c0\ub9c9 \uc22b\uc790\ub294 last-1 \ub610\ub294 last+1\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ub97c \uc218\uc2dd\uc73c\ub85c \ud45c\ud604\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4. <\/p>\n
\n dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]\n <\/pre>\n \uc5ec\uae30\uc11c last\ub294 1\ubd80\ud130 8\uae4c\uc9c0\uc758 \ubc94\uc704\ub97c \uac00\uc9c8 \uc218 \uc788\uc2b5\ub2c8\ub2e4(0\uacfc 9\ub294 \uac01\uac01 \ud55c\ucabd\uc5d0 \ud55c\uc815\ub418\ubbc0\ub85c).\n <\/li>\n
- \n\uacb0\uacfc \uacc4\uc0b0<\/strong>: N\uc790\ub9ac \uc218\uc758 \uac1c\uc218\ub294 dp[N][0] + dp[N][1] + … + dp[N][9]\uc758 \ud569\uc785\ub2c8\ub2e4. \uadf8\ub7ec\ub098 \ubb38\uc81c\uc5d0\uc11c \uc694\uad6c\ud558\ub294 \uac83\uc740 10007\ub85c \ub098\ub208 \ub098\uba38\uc9c0\uc774\ubbc0\ub85c, \uacc4\uc0b0 \uacfc\uc815\uc5d0\uc11c \uc774 \uc5f0\uc0b0\uc744 \uc218\ud589\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/li>\n<\/ol>\n<\/section>\n
\n\uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h2>\n\n import java.util.Scanner;\n\n public class StairNumber {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int N = sc.nextInt();\n int MOD = 10007;\n\n \/\/ DP \ubc30\uc5f4 \ucd08\uae30\ud654\n int[][] dp = new int[N + 1][10];\n\n \/\/ 1\uc790\ub9ac \uc218 \ucd08\uae30\ud654\n for (int i = 1; i < 10; i++) {\n dp[1][i] = 1;\n }\n\n \/\/ DP \ud14c\uc774\ube14 \uad6c\uc131\n for (int n = 2; n <= N; n++) {\n for (int last = 0; last <= 9; last++) {\n if (last > 0) { \/\/ last\uac00 0\uc774 \uc544\ub2d0 \uacbd\uc6b0\n dp[n][last] += dp[n - 1][last - 1];\n }\n if (last < 9) { \/\/ last\uac00 9\uac00 \uc544\ub2d0 \uacbd\uc6b0\n dp[n][last] += dp[n - 1][last + 1];\n }\n dp[n][last] %= MOD; \/\/ MOD \uc5f0\uc0b0\n }\n }\n\n \/\/ \uacb0\uacfc \ud569\uc0b0\n int result = 0;\n for (int last = 0; last <= 9; last++) {\n result = (result + dp[N][last]) % MOD;\n }\n\n \/\/ \uacb0\uacfc \ucd9c\ub825\n System.out.println(result);\n sc.close();\n }\n }\n <\/pre>\n<\/section>\n\n\uc608\uc2dc<\/h2>\n\uc785\ub825<\/h3>\n3<\/pre>\n\ucd9c\ub825<\/h3>\n14<\/pre>\n\uc704\uc758 \ucf54\ub4dc\ub97c \uc2e4\ud589\ud558\uac8c \ub418\uba74, 3\uc790\ub9ac \uacc4\ub2e8 \uc218\uc758 \uac1c\uc218\ub97c \uc815\ud655\ud558\uac8c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\ucd94\uac00 \uc0ac\ud56d<\/h2>\n
\n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uace0 \ub09c \ud6c4, \ub2e4\uc591\ud55c \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\ub85c \uc54c\uace0\ub9ac\uc998\uc758 \uc815\ud655\uc131\uc744 \uac80\uc99d\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \ub610\ud55c \ucf54\ub4dc\ub97c \ucd5c\uc801\ud654\ud558\uac70\ub098 \ub2e4\uc591\ud55c \ubc29\ubc95\uc73c\ub85c \uc54c\uace0\ub9ac\uc998\uc744 \uc811\uadfc\ud558\uc5ec \uadf8 \uacb0\uacfc\ub97c \ube44\uad50\ud558\ub294 \uac83\ub3c4 \uc88b\uc740 \ubc29\ubc95\uc785\ub2c8\ub2e4.\n <\/p>\n
\n \ub9c8\uc9c0\ub9c9\uc73c\ub85c, \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d \ubb38\uc81c\ub294 \ub9ce\uc740 \uacbd\uc6b0 \uadf8\ub798\ud504 \uc774\ub860\uacfc\ub3c4 \uc5f0\uacb0\ub420 \uc218 \uc788\uc73c\ub2c8, \ud56d\uc0c1 \uc774\ub7ec\ud55c \uad00\uc810\uc744 \uac16\uace0 \ubb38\uc81c\ub97c \ud478\uc154\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n
<\/main><\/p>\n
\uc608\uc81c \uc785\ub825<\/h3>\n3<\/pre>\n\uc608\uc81c \ucd9c\ub825<\/h3>\n14<\/pre>\n\uc124\uba85<\/h3>\n
\n N\uc774 3\uc774\uba74, 3\uc790\ub9ac \uacc4\ub2e8 \uc218\ub294 123, 132, 210, 321, 234, 345, 456, 567, 678, 789 \ub4f1 \ucd1d 14\uac1c\uac00 \uc874\uc7ac\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n\n\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
\n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming)\uc758 \uae30\ubc95\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n \uacc4\ub2e8 \uc218\ub294 \uc774\uc804 N-1\uc790\ub9ac \uc218\ub97c \uae30\ubc18\uc73c\ub85c \ud55c N\uc790\ub9ac \uc218\uc758 \uc870\ud569\uc73c\ub85c \uc0dd\uac01\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. N-1\uc790\ub9ac \uc218\uc758 \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uc5d0 \ub530\ub77c N\uc790\ub9ac \uc218\uc758 \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uac00 \uacb0\uc815\ub418\ubbc0\ub85c, \uc774\ub97c \uace0\ub824\ud558\uc5ec DP \ubc30\uc5f4\uc744 \uc5c5\ub370\uc774\ud2b8\ud558\uba74 \ub429\ub2c8\ub2e4.\n <\/p>\n
\ud480\uc774 \uc811\uadfc \ubc29\uc2dd<\/h3>\n\n- \n\uc0c1\ud0dc \uc815\uc758<\/strong>: dp[n][last]\ub97c n\uc790\ub9ac \uacc4\ub2e8 \uc218 \uc911 \ub9c8\uc9c0\ub9c9 \uc790\ub9ac \uc218\uac00 last\uc778 \uacbd\uc6b0\uc758 \uac1c\uc218\ub85c \uc815\uc758\ud569\ub2c8\ub2e4. n\uc740 \uc790\ub9ac \uc218\ub97c \uc758\ubbf8\ud558\uba70, last\ub294 \ub9c8\uc9c0\ub9c9 \uc22b\uc790(0~9)\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4.\n <\/li>\n
- \n\ucd08\uae30 \uc0c1\ud0dc \uc124\uc815<\/strong>: 1\uc790\ub9ac \uc218\uc758 \uacbd\uc6b0(\uc989, N=1\uc77c \ub54c) \uac01 \uc22b\uc790(1~9)\ub294 \uac01\uae30 1\uac1c\uc758 \uacbd\uc6b0\uc758 \uc218\ub97c \uac00\uc9d1\ub2c8\ub2e4. \ub530\ub77c\uc11c dp[1][1] ~ dp[1][9]\ub294 1, dp[1][0]\ub294 0\uc785\ub2c8\ub2e4.\n <\/li>\n
- \n\uc0c1\ud0dc \uc804\uc774<\/strong>: n\uc790\ub9ac \uc218\ub294 n-1\uc790\ub9ac \uc218\uc5d0\uc11c \ub9cc\ub4e4\uc5b4\uc9d1\ub2c8\ub2e4. \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uac00 last\uc77c \ub54c, \ub9c8\uc9c0\ub9c9 \uc22b\uc790\ub294 last-1 \ub610\ub294 last+1\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ub97c \uc218\uc2dd\uc73c\ub85c \ud45c\ud604\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4. <\/p>\n
\n dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]\n <\/pre>\n \uc5ec\uae30\uc11c last\ub294 1\ubd80\ud130 8\uae4c\uc9c0\uc758 \ubc94\uc704\ub97c \uac00\uc9c8 \uc218 \uc788\uc2b5\ub2c8\ub2e4(0\uacfc 9\ub294 \uac01\uac01 \ud55c\ucabd\uc5d0 \ud55c\uc815\ub418\ubbc0\ub85c).\n <\/li>\n
- \n\uacb0\uacfc \uacc4\uc0b0<\/strong>: N\uc790\ub9ac \uc218\uc758 \uac1c\uc218\ub294 dp[N][0] + dp[N][1] + … + dp[N][9]\uc758 \ud569\uc785\ub2c8\ub2e4. \uadf8\ub7ec\ub098 \ubb38\uc81c\uc5d0\uc11c \uc694\uad6c\ud558\ub294 \uac83\uc740 10007\ub85c \ub098\ub208 \ub098\uba38\uc9c0\uc774\ubbc0\ub85c, \uacc4\uc0b0 \uacfc\uc815\uc5d0\uc11c \uc774 \uc5f0\uc0b0\uc744 \uc218\ud589\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/li>\n<\/ol>\n<\/section>\n
\n\uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h2>\n\n import java.util.Scanner;\n\n public class StairNumber {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int N = sc.nextInt();\n int MOD = 10007;\n\n \/\/ DP \ubc30\uc5f4 \ucd08\uae30\ud654\n int[][] dp = new int[N + 1][10];\n\n \/\/ 1\uc790\ub9ac \uc218 \ucd08\uae30\ud654\n for (int i = 1; i < 10; i++) {\n dp[1][i] = 1;\n }\n\n \/\/ DP \ud14c\uc774\ube14 \uad6c\uc131\n for (int n = 2; n <= N; n++) {\n for (int last = 0; last <= 9; last++) {\n if (last > 0) { \/\/ last\uac00 0\uc774 \uc544\ub2d0 \uacbd\uc6b0\n dp[n][last] += dp[n - 1][last - 1];\n }\n if (last < 9) { \/\/ last\uac00 9\uac00 \uc544\ub2d0 \uacbd\uc6b0\n dp[n][last] += dp[n - 1][last + 1];\n }\n dp[n][last] %= MOD; \/\/ MOD \uc5f0\uc0b0\n }\n }\n\n \/\/ \uacb0\uacfc \ud569\uc0b0\n int result = 0;\n for (int last = 0; last <= 9; last++) {\n result = (result + dp[N][last]) % MOD;\n }\n\n \/\/ \uacb0\uacfc \ucd9c\ub825\n System.out.println(result);\n sc.close();\n }\n }\n <\/pre>\n<\/section>\n\n\uc608\uc2dc<\/h2>\n\uc785\ub825<\/h3>\n3<\/pre>\n\ucd9c\ub825<\/h3>\n14<\/pre>\n\uc704\uc758 \ucf54\ub4dc\ub97c \uc2e4\ud589\ud558\uac8c \ub418\uba74, 3\uc790\ub9ac \uacc4\ub2e8 \uc218\uc758 \uac1c\uc218\ub97c \uc815\ud655\ud558\uac8c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\ucd94\uac00 \uc0ac\ud56d<\/h2>\n
\n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uace0 \ub09c \ud6c4, \ub2e4\uc591\ud55c \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\ub85c \uc54c\uace0\ub9ac\uc998\uc758 \uc815\ud655\uc131\uc744 \uac80\uc99d\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \ub610\ud55c \ucf54\ub4dc\ub97c \ucd5c\uc801\ud654\ud558\uac70\ub098 \ub2e4\uc591\ud55c \ubc29\ubc95\uc73c\ub85c \uc54c\uace0\ub9ac\uc998\uc744 \uc811\uadfc\ud558\uc5ec \uadf8 \uacb0\uacfc\ub97c \ube44\uad50\ud558\ub294 \uac83\ub3c4 \uc88b\uc740 \ubc29\ubc95\uc785\ub2c8\ub2e4.\n <\/p>\n
\n \ub9c8\uc9c0\ub9c9\uc73c\ub85c, \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d \ubb38\uc81c\ub294 \ub9ce\uc740 \uacbd\uc6b0 \uadf8\ub798\ud504 \uc774\ub860\uacfc\ub3c4 \uc5f0\uacb0\ub420 \uc218 \uc788\uc73c\ub2c8, \ud56d\uc0c1 \uc774\ub7ec\ud55c \uad00\uc810\uc744 \uac16\uace0 \ubb38\uc81c\ub97c \ud478\uc154\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n
<\/main><\/p>\n
\uc608\uc81c \ucd9c\ub825<\/h3>\n14<\/pre>\n\uc124\uba85<\/h3>\n
\n N\uc774 3\uc774\uba74, 3\uc790\ub9ac \uacc4\ub2e8 \uc218\ub294 123, 132, 210, 321, 234, 345, 456, 567, 678, 789 \ub4f1 \ucd1d 14\uac1c\uac00 \uc874\uc7ac\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n\n\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
\n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming)\uc758 \uae30\ubc95\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n \uacc4\ub2e8 \uc218\ub294 \uc774\uc804 N-1\uc790\ub9ac \uc218\ub97c \uae30\ubc18\uc73c\ub85c \ud55c N\uc790\ub9ac \uc218\uc758 \uc870\ud569\uc73c\ub85c \uc0dd\uac01\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. N-1\uc790\ub9ac \uc218\uc758 \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uc5d0 \ub530\ub77c N\uc790\ub9ac \uc218\uc758 \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uac00 \uacb0\uc815\ub418\ubbc0\ub85c, \uc774\ub97c \uace0\ub824\ud558\uc5ec DP \ubc30\uc5f4\uc744 \uc5c5\ub370\uc774\ud2b8\ud558\uba74 \ub429\ub2c8\ub2e4.\n <\/p>\n
\ud480\uc774 \uc811\uadfc \ubc29\uc2dd<\/h3>\n\n- \n\uc0c1\ud0dc \uc815\uc758<\/strong>: dp[n][last]\ub97c n\uc790\ub9ac \uacc4\ub2e8 \uc218 \uc911 \ub9c8\uc9c0\ub9c9 \uc790\ub9ac \uc218\uac00 last\uc778 \uacbd\uc6b0\uc758 \uac1c\uc218\ub85c \uc815\uc758\ud569\ub2c8\ub2e4. n\uc740 \uc790\ub9ac \uc218\ub97c \uc758\ubbf8\ud558\uba70, last\ub294 \ub9c8\uc9c0\ub9c9 \uc22b\uc790(0~9)\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4.\n <\/li>\n
- \n\ucd08\uae30 \uc0c1\ud0dc \uc124\uc815<\/strong>: 1\uc790\ub9ac \uc218\uc758 \uacbd\uc6b0(\uc989, N=1\uc77c \ub54c) \uac01 \uc22b\uc790(1~9)\ub294 \uac01\uae30 1\uac1c\uc758 \uacbd\uc6b0\uc758 \uc218\ub97c \uac00\uc9d1\ub2c8\ub2e4. \ub530\ub77c\uc11c dp[1][1] ~ dp[1][9]\ub294 1, dp[1][0]\ub294 0\uc785\ub2c8\ub2e4.\n <\/li>\n
- \n\uc0c1\ud0dc \uc804\uc774<\/strong>: n\uc790\ub9ac \uc218\ub294 n-1\uc790\ub9ac \uc218\uc5d0\uc11c \ub9cc\ub4e4\uc5b4\uc9d1\ub2c8\ub2e4. \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uac00 last\uc77c \ub54c, \ub9c8\uc9c0\ub9c9 \uc22b\uc790\ub294 last-1 \ub610\ub294 last+1\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ub97c \uc218\uc2dd\uc73c\ub85c \ud45c\ud604\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4. <\/p>\n
\n dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]\n <\/pre>\n \uc5ec\uae30\uc11c last\ub294 1\ubd80\ud130 8\uae4c\uc9c0\uc758 \ubc94\uc704\ub97c \uac00\uc9c8 \uc218 \uc788\uc2b5\ub2c8\ub2e4(0\uacfc 9\ub294 \uac01\uac01 \ud55c\ucabd\uc5d0 \ud55c\uc815\ub418\ubbc0\ub85c).\n <\/li>\n
- \n\uacb0\uacfc \uacc4\uc0b0<\/strong>: N\uc790\ub9ac \uc218\uc758 \uac1c\uc218\ub294 dp[N][0] + dp[N][1] + … + dp[N][9]\uc758 \ud569\uc785\ub2c8\ub2e4. \uadf8\ub7ec\ub098 \ubb38\uc81c\uc5d0\uc11c \uc694\uad6c\ud558\ub294 \uac83\uc740 10007\ub85c \ub098\ub208 \ub098\uba38\uc9c0\uc774\ubbc0\ub85c, \uacc4\uc0b0 \uacfc\uc815\uc5d0\uc11c \uc774 \uc5f0\uc0b0\uc744 \uc218\ud589\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/li>\n<\/ol>\n<\/section>\n
\n\uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h2>\n\n import java.util.Scanner;\n\n public class StairNumber {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int N = sc.nextInt();\n int MOD = 10007;\n\n \/\/ DP \ubc30\uc5f4 \ucd08\uae30\ud654\n int[][] dp = new int[N + 1][10];\n\n \/\/ 1\uc790\ub9ac \uc218 \ucd08\uae30\ud654\n for (int i = 1; i < 10; i++) {\n dp[1][i] = 1;\n }\n\n \/\/ DP \ud14c\uc774\ube14 \uad6c\uc131\n for (int n = 2; n <= N; n++) {\n for (int last = 0; last <= 9; last++) {\n if (last > 0) { \/\/ last\uac00 0\uc774 \uc544\ub2d0 \uacbd\uc6b0\n dp[n][last] += dp[n - 1][last - 1];\n }\n if (last < 9) { \/\/ last\uac00 9\uac00 \uc544\ub2d0 \uacbd\uc6b0\n dp[n][last] += dp[n - 1][last + 1];\n }\n dp[n][last] %= MOD; \/\/ MOD \uc5f0\uc0b0\n }\n }\n\n \/\/ \uacb0\uacfc \ud569\uc0b0\n int result = 0;\n for (int last = 0; last <= 9; last++) {\n result = (result + dp[N][last]) % MOD;\n }\n\n \/\/ \uacb0\uacfc \ucd9c\ub825\n System.out.println(result);\n sc.close();\n }\n }\n <\/pre>\n<\/section>\n\n\uc608\uc2dc<\/h2>\n\uc785\ub825<\/h3>\n3<\/pre>\n\ucd9c\ub825<\/h3>\n14<\/pre>\n\uc704\uc758 \ucf54\ub4dc\ub97c \uc2e4\ud589\ud558\uac8c \ub418\uba74, 3\uc790\ub9ac \uacc4\ub2e8 \uc218\uc758 \uac1c\uc218\ub97c \uc815\ud655\ud558\uac8c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\ucd94\uac00 \uc0ac\ud56d<\/h2>\n
\n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uace0 \ub09c \ud6c4, \ub2e4\uc591\ud55c \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\ub85c \uc54c\uace0\ub9ac\uc998\uc758 \uc815\ud655\uc131\uc744 \uac80\uc99d\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \ub610\ud55c \ucf54\ub4dc\ub97c \ucd5c\uc801\ud654\ud558\uac70\ub098 \ub2e4\uc591\ud55c \ubc29\ubc95\uc73c\ub85c \uc54c\uace0\ub9ac\uc998\uc744 \uc811\uadfc\ud558\uc5ec \uadf8 \uacb0\uacfc\ub97c \ube44\uad50\ud558\ub294 \uac83\ub3c4 \uc88b\uc740 \ubc29\ubc95\uc785\ub2c8\ub2e4.\n <\/p>\n
\n \ub9c8\uc9c0\ub9c9\uc73c\ub85c, \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d \ubb38\uc81c\ub294 \ub9ce\uc740 \uacbd\uc6b0 \uadf8\ub798\ud504 \uc774\ub860\uacfc\ub3c4 \uc5f0\uacb0\ub420 \uc218 \uc788\uc73c\ub2c8, \ud56d\uc0c1 \uc774\ub7ec\ud55c \uad00\uc810\uc744 \uac16\uace0 \ubb38\uc81c\ub97c \ud478\uc154\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n
<\/main><\/p>\n
\uc124\uba85<\/h3>\n
\n N\uc774 3\uc774\uba74, 3\uc790\ub9ac \uacc4\ub2e8 \uc218\ub294 123, 132, 210, 321, 234, 345, 456, 567, 678, 789 \ub4f1 \ucd1d 14\uac1c\uac00 \uc874\uc7ac\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n \n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming)\uc758 \uae30\ubc95\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \uacc4\ub2e8 \uc218\ub294 \uc774\uc804 N-1\uc790\ub9ac \uc218\ub97c \uae30\ubc18\uc73c\ub85c \ud55c N\uc790\ub9ac \uc218\uc758 \uc870\ud569\uc73c\ub85c \uc0dd\uac01\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. N-1\uc790\ub9ac \uc218\uc758 \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uc5d0 \ub530\ub77c N\uc790\ub9ac \uc218\uc758 \ub9c8\uc9c0\ub9c9 \uc22b\uc790\uac00 \uacb0\uc815\ub418\ubbc0\ub85c, \uc774\ub97c \uace0\ub824\ud558\uc5ec DP \ubc30\uc5f4\uc744 \uc5c5\ub370\uc774\ud2b8\ud558\uba74 \ub429\ub2c8\ub2e4.\n <\/p>\n \uc5ec\uae30\uc11c last\ub294 1\ubd80\ud130 8\uae4c\uc9c0\uc758 \ubc94\uc704\ub97c \uac00\uc9c8 \uc218 \uc788\uc2b5\ub2c8\ub2e4(0\uacfc 9\ub294 \uac01\uac01 \ud55c\ucabd\uc5d0 \ud55c\uc815\ub418\ubbc0\ub85c).\n <\/li>\n \uc704\uc758 \ucf54\ub4dc\ub97c \uc2e4\ud589\ud558\uac8c \ub418\uba74, 3\uc790\ub9ac \uacc4\ub2e8 \uc218\uc758 \uac1c\uc218\ub97c \uc815\ud655\ud558\uac8c \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n \n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uace0 \ub09c \ud6c4, \ub2e4\uc591\ud55c \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\ub85c \uc54c\uace0\ub9ac\uc998\uc758 \uc815\ud655\uc131\uc744 \uac80\uc99d\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \ub610\ud55c \ucf54\ub4dc\ub97c \ucd5c\uc801\ud654\ud558\uac70\ub098 \ub2e4\uc591\ud55c \ubc29\ubc95\uc73c\ub85c \uc54c\uace0\ub9ac\uc998\uc744 \uc811\uadfc\ud558\uc5ec \uadf8 \uacb0\uacfc\ub97c \ube44\uad50\ud558\ub294 \uac83\ub3c4 \uc88b\uc740 \ubc29\ubc95\uc785\ub2c8\ub2e4.\n <\/p>\n \n \ub9c8\uc9c0\ub9c9\uc73c\ub85c, \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d \ubb38\uc81c\ub294 \ub9ce\uc740 \uacbd\uc6b0 \uadf8\ub798\ud504 \uc774\ub860\uacfc\ub3c4 \uc5f0\uacb0\ub420 \uc218 \uc788\uc73c\ub2c8, \ud56d\uc0c1 \uc774\ub7ec\ud55c \uad00\uc810\uc744 \uac16\uace0 \ubb38\uc81c\ub97c \ud478\uc154\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n <\/main><\/p>\n\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
\ud480\uc774 \uc811\uadfc \ubc29\uc2dd<\/h3>\n
\n
\n dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]\n <\/pre>\n
\uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\n import java.util.Scanner;\n\n public class StairNumber {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int N = sc.nextInt();\n int MOD = 10007;\n\n \/\/ DP \ubc30\uc5f4 \ucd08\uae30\ud654\n int[][] dp = new int[N + 1][10];\n\n \/\/ 1\uc790\ub9ac \uc218 \ucd08\uae30\ud654\n for (int i = 1; i < 10; i++) {\n dp[1][i] = 1;\n }\n\n \/\/ DP \ud14c\uc774\ube14 \uad6c\uc131\n for (int n = 2; n <= N; n++) {\n for (int last = 0; last <= 9; last++) {\n if (last > 0) { \/\/ last\uac00 0\uc774 \uc544\ub2d0 \uacbd\uc6b0\n dp[n][last] += dp[n - 1][last - 1];\n }\n if (last < 9) { \/\/ last\uac00 9\uac00 \uc544\ub2d0 \uacbd\uc6b0\n dp[n][last] += dp[n - 1][last + 1];\n }\n dp[n][last] %= MOD; \/\/ MOD \uc5f0\uc0b0\n }\n }\n\n \/\/ \uacb0\uacfc \ud569\uc0b0\n int result = 0;\n for (int last = 0; last <= 9; last++) {\n result = (result + dp[N][last]) % MOD;\n }\n\n \/\/ \uacb0\uacfc \ucd9c\ub825\n System.out.println(result);\n sc.close();\n }\n }\n <\/pre>\n<\/section>\n\uc608\uc2dc<\/h2>\n
\uc785\ub825<\/h3>\n
3<\/pre>\n
\ucd9c\ub825<\/h3>\n
14<\/pre>\n
\ucd94\uac00 \uc0ac\ud56d<\/h2>\n