\ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ub294 \ubb38\uc81c \uc911 \ud558\ub098\ub294 \uc8fc\uc5b4\uc9c4 \uc815\uc218\ub97c 1\ub85c \ub9cc\ub4dc\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. \uc774 \uac15\uc88c\uc5d0\uc11c\ub294 \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \ud544\uc694\ud55c \uc54c\uace0\ub9ac\uc998, \uc811\uadfc\ubc95, \uadf8\ub9ac\uace0 \uc2e4\uc81c \ucf54\ub529 \uc608\uc81c\ub97c \ud1b5\ud574 \uc790\uc138\ud788 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4. \uc6b0\ub9ac\uc758 \ubaa9\ud45c\ub294 \uc8fc\uc5b4\uc9c4 \uc815\uc218\uac00 1\uc774 \ub420 \ub54c\uae4c\uc9c0 \ucd5c\uc18c\ud55c\uc758 \uc5f0\uc0b0\uc744 \uc218\ud589\ud558\ub294 \uac83\uc785\ub2c8\ub2e4.<\/p>\n
\uc8fc\uc5b4\uc9c4 \uc815\uc218 \uc608\ub97c \ub4e4\uc5b4, \ub530\ub77c\uc11c, \ucd1d \uc5f0\uc0b0 \ud69f\uc218\ub294 3\uc774 \ub429\ub2c8\ub2e4.<\/p>\n \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc73c\ub85c \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc120 DP(\ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d)\ub97c \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. DP\ub294 \ubb38\uc81c\ub97c \uc791\uc740 \ubd80\ubd84 \ubb38\uc81c\ub85c \ub098\ub204\uace0, \uac01 \ubd80\ubd84 \ubb38\uc81c\uc758 \ud574\ub2f5\uc744 \uc800\uc7a5\ud574 \uc911\ubcf5 \uacc4\uc0b0\uc744 \uc904\uc774\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4. \uc544\ub798 \uacfc\uc815\uc744 \ud1b5\ud574 \uc774 \uc811\uadfc\ubc95\uc744 \uc790\uc138\ud788 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n DP \ud14c\uc774\ube14\uc744 \uc0dd\uc131\ud558\uc5ec \uac01 \uc778\ub371\uc2a4 \uae30\ubcf8\uc801\uc73c\ub85c \uac01 \uc815\uc218 \uc989, \uc6b0\ub9ac\ub294 \ubaa8\ub4e0 \uc815\uc218\uc5d0 \ub300\ud574 DP \ud14c\uc774\ube14\uc744 \ub2e4 \ucc44\uc6b4 \ub4a4, \uc544\ub798\ub294 \uc55e\uc11c \uc124\uba85\ud55c \ub0b4\uc6a9\uc744 \ubc14\ud0d5\uc73c\ub85c \uc791\uc131\ud55c \uc804\uccb4 \ucf54\ub4dc\uc785\ub2c8\ub2e4:<\/p>\nX<\/code>\uac00 \uc788\uc2b5\ub2c8\ub2e4. \ub2e4\uc74c\uc758 \uc138 \uac00\uc9c0 \uc5f0\uc0b0\uc744 \uc774\uc6a9\ud558\uc5ec \uc774 X<\/code>\ub97c 1\ub85c \ub9cc\ub4e4\uace0, \ud544\uc694\ud55c \ucd5c\uc18c \uc5f0\uc0b0\uc758 \ud69f\uc218\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4:<\/p>\n\n
X - 1<\/code><\/li>\nX \/ 2<\/code> (\ub2e8, X\uac00 2\ub85c \ub098\ub204\uc5b4\ub5a8\uc5b4\uc9c8 \ub54c\ub9cc \uac00\ub2a5)<\/li>\nX \/ 3<\/code> (\ub2e8, X\uac00 3\uc73c\ub85c \ub098\ub204\uc5b4\ub5a8\uc5b4\uc9c8 \ub54c\ub9cc \uac00\ub2a5)<\/li>\n<\/ul>\nX = 10<\/code>\uc77c \ub54c, \ub2e4\uc74c\uacfc \uac19\uc774 \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n\n
\ubb38\uc81c \ud574\uacb0 \uc811\uadfc\ubc95<\/h2>\n
1\ub2e8\uacc4: DP \ud14c\uc774\ube14 \ucd08\uae30\ud654<\/h3>\n
i<\/code>\uc5d0 \ub300\ud574 i<\/code>\ub97c 1\ub85c \ub9cc\ub4dc\ub294 \ub370 \ud544\uc694\ud55c \ucd5c\uc18c \uc5f0\uc0b0 \ud69f\uc218\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4. \ud14c\uc774\ube14\uc758 \ud06c\uae30\ub294 X + 1<\/code>\ub85c \uc124\uc815\ud569\ub2c8\ub2e4.<\/p>\n\nX = int(input(\"\uc815\uc218\ub97c \uc785\ub825\ud558\uc138\uc694: \"))\ndp = [0] * (X + 1)\n <\/pre>\n
2\ub2e8\uacc4: \uae30\uc800 \uc0ac\ub840 \uc124\uc815<\/h3>\n
dp[1]<\/code>\uc758 \uac12\uc740 0\uc785\ub2c8\ub2e4. \uc65c\ub0d0\ud558\uba74, 1\uc740 \uc774\ubbf8 \ubaa9\ud45c\uc774\ubbc0\ub85c \ucd94\uac00\uc801\uc778 \uc5f0\uc0b0\uc774 \ud544\uc694 \uc5c6\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4.<\/p>\n\ndp[1] = 0 # 1\uc740 0\ubc88\uc758 \uc5f0\uc0b0\uc73c\ub85c \ub098\ud0c0\ub0bc \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/pre>\n
3\ub2e8\uacc4: \uc810\ud654\uc2dd \uc124\uc815<\/h3>\n
i<\/code>\uc5d0 \ub300\ud558\uc5ec \uac00\ub2a5\ud55c \ubaa8\ub4e0 \uc5f0\uc0b0\uc744 \uc218\ud589\ud574 dp[i]<\/code>\uc758 \uac12\uc744 \uc5c5\ub370\uc774\ud2b8\ud569\ub2c8\ub2e4.<\/p>\n\n
i<\/code>\uc5d0\uc11c 1\uc744 \ube7c\ub294 \uacbd\uc6b0: dp[i] = dp[i-1] + 1<\/code><\/li>\ni<\/code>\uac00 2\ub85c \ub098\ub204\uc5b4\ub5a8\uc5b4\uc9c8 \ub54c: dp[i] = min(dp[i], dp[i \/\/ 2] + 1)<\/code><\/li>\ni<\/code>\uac00 3\uc73c\ub85c \ub098\ub204\uc5b4\ub5a8\uc5b4\uc9c8 \ub54c: dp[i] = min(dp[i], dp[i \/\/ 3] + 1)<\/code><\/li>\n<\/ul>\ndp[i]<\/code>\uc758 \uac12\uc744 \ucd5c\uc18c\ud55c\uc758 \uc5f0\uc0b0\uc73c\ub85c \uc5c5\ub370\uc774\ud2b8\ud574 \ub098\uac00\ub294 \uac83\uc785\ub2c8\ub2e4.<\/p>\n4\ub2e8\uacc4: \ucd5c\uc885 \uacb0\uacfc \ub3c4\ucd9c<\/h3>\n
dp[X]<\/code>\uac00 \uc6b0\ub9ac\uac00 \uc6d0\ud558\ub294 \uacb0\uacfc, \uc989 X<\/code>\ub97c 1\ub85c \ub9cc\ub4dc\ub294 \ub370 \ud544\uc694\ud55c \ucd5c\uc18c \uc5f0\uc0b0 \ud69f\uc218\uac00 \ub429\ub2c8\ub2e4.<\/p>\n\nfor i in range(2, X + 1):\n dp[i] = dp[i - 1] + 1\n if i % 2 == 0:\n dp[i] = min(dp[i], dp[i \/\/ 2] + 1)\n if i % 3 == 0:\n dp[i] = min(dp[i], dp[i \/\/ 3] + 1)\n\nprint(\"\ucd5c\uc18c \uc5f0\uc0b0 \ud69f\uc218:\", dp[X])\n <\/pre>\n
\uc804\uccb4 \ucf54\ub4dc<\/h2>\n
\ndef min_operations_to_one(X):\n dp = [0] * (X + 1)\n dp[1] = 0 # \uae30\uc800 \uc0ac\ub840: 1\uc740 0\ubc88\uc758 \uc5f0\uc0b0\uc73c\ub85c \ub098\ud0c0\ub0bc \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n\n for i in range(2, X + 1):\n dp[i] = dp[i - 1] + 1 # 1\uc744 \ube84 \uacbd\uc6b0\n if i % 2 == 0:\n dp[i] = min(dp[i], dp[i \/\/ 2] + 1) # 2\ub85c \ub098\ub20c \uacbd\uc6b0\n if i % 3 == 0:\n dp[i] = min(dp[i], dp[i \/\/ 3] + 1) # 3\uc73c\ub85c \ub098\ub20c \uacbd\uc6b0\n\n return dp[X]\n\n# \uc0ac\uc6a9\uc790 \uc785\ub825\nX = int(input(\"\uc815\uc218\ub97c \uc785\ub825\ud558\uc138\uc694: \"))\nresult = min_operations_to_one(X)\nprint(\"\ucd5c\uc18c \uc5f0\uc0b0 \ud69f\uc218:\", result)\n <\/pre>\n
\ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n