https:\/\/www.acmicpc.net\/problem\/1463<\/a><\/a><\/p>\n \uc815\uc218 X\uc5d0 \uc0ac\uc6a9\ud560 \uc218 \uc788\ub294 \uc5f0\uc0b0\uc740 \ub2e4\uc74c\uacfc \uac19\uc774 \uc138 \uac00\uc9c0 \uc774\ub2e4.<\/p>\n \uc815\uc218 N\uc774 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \uc704\uc640 \uac19\uc740 \uc5f0\uc0b0 \uc138 \uac1c\ub97c \uc801\uc808\ud788 \uc0ac\uc6a9\ud574\uc11c 1\uc744 \ub9cc\ub4e4\ub824\uace0 \ud55c\ub2e4. \uc5f0\uc0b0\uc744 \uc0ac\uc6a9\ud558\ub294 \ud69f\uc218\uc758 \ucd5c\uc19f\uac12\uc744 \ucd9c\ub825\ud558\uc2dc\uc624.<\/p>\n \uccab\uc9f8 \uc904\uc5d0 1\ubcf4\ub2e4 \ud06c\uac70\ub098 \uac19\uace0, 106\ubcf4\ub2e4 \uc791\uac70\ub098 \uac19\uc740 \uc815\uc218 N\uc774 \uc8fc\uc5b4\uc9c4\ub2e4.<\/p>\n \uccab\uc9f8 \uc904\uc5d0 \uc5f0\uc0b0\uc744 \ud558\ub294 \ud69f\uc218\uc758 \ucd5c\uc19f\uac12\uc744 \ucd9c\ub825\ud55c\ub2e4.<\/p>\n bottom-up \ubc29\uc2dd\uc73c\ub85c d[] \ub97c \ucc44\uc6cc\ub098\uac04\ub2e4. BaekJoon Online Judge 1463: 1\ub85c \ub9cc\ub4e4\uae30 \ubb38\uc81c https:\/\/www.acmicpc.net\/problem\/1463 \uc815\uc218 X\uc5d0 \uc0ac\uc6a9\ud560 \uc218 \uc788\ub294 \uc5f0\uc0b0\uc740 \ub2e4\uc74c\uacfc \uac19\uc774 \uc138 \uac00\uc9c0 \uc774\ub2e4. X\uac00 3\uc73c\ub85c \ub098\ub204\uc5b4 \ub5a8\uc5b4\uc9c0\uba74, 3\uc73c\ub85c \ub098\ub208\ub2e4. X\uac00 2\ub85c \ub098\ub204\uc5b4 \ub5a8\uc5b4\uc9c0\uba74, 2\ub85c \ub098\ub208\ub2e4. 1\uc744 \ube80\ub2e4. \uc815\uc218 N\uc774 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \uc704\uc640 \uac19\uc740 \uc5f0\uc0b0 \uc138 \uac1c\ub97c \uc801\uc808\ud788 \uc0ac\uc6a9\ud574\uc11c 1\uc744 \ub9cc\ub4e4\ub824\uace0 \ud55c\ub2e4. \uc5f0\uc0b0\uc744 \uc0ac\uc6a9\ud558\ub294 \ud69f\uc218\uc758 \ucd5c\uc19f\uac12\uc744 \ucd9c\ub825\ud558\uc2dc\uc624. \uc785\ub825 \uccab\uc9f8 \uc904\uc5d0 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22],"tags":[34,95],"class_list":["post-543","post","type-post","status-publish","format-standard","hentry","category-baekjoon-online-judge","tag-python","tag-95"],"_links":{"self":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/543","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/comments?post=543"}],"version-history":[{"count":3,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/543\/revisions"}],"predecessor-version":[{"id":1281,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/543\/revisions\/1281"}],"wp:attachment":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/media?parent=543"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/categories?post=543"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/tags?post=543"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n
\uc785\ub825<\/h3>\n
\ucd9c\ub825<\/h3>\n
\uc18c\uc2a4\ucf54\ub4dc<\/h2>\n
n = int(input())\nd = [0]*(n+1)\nfor i in range(2,n+1):\n d[i] = d[i-1] + 1\n if (i%2==0 and d[i]>d[i\/\/2]+1): d[i]=d[i\/\/2]+1\n if (i%3==0 and d[i]>d[i\/\/3]+1): d[i]=d[i\/\/3]+1\n#print(d)\nprint(d[n])\n<\/code><\/pre>\n
\n\ub9e4 \ub8e8\ud504\uc5d0\uc11c, \uc55e \uc790\ub9ac\uc758 \uc218\uc5d0 1\uc744 \ub354\ud55c \uac83\uc774 \uac00\uc7a5 \ube68\ub9ac 1\ub85c \ub9cc\ub4dc\ub294 \ubc29\ubc95\uc774\ub77c \uac00\uc815\ud558\uace0 \uc2dc\uc791\ud558\uc5ec, \uc774\ud6c4 2\ub85c \ub098\ub208 \uc218\uc640 3\uc73c\ub85c \ub098\ub208 \uc218\uc5d0 1\uc744 \ub354\ud55c \uac83\uacfc \ubaa8\ub450 \ube44\uad50\ud574\uc11c \uac00\uc7a5 \uc791\uc740 \uc218\ub97c d[n]\uc5d0 \ub300\uc785\ud55c\ub2e4.<\/p>\n","protected":false},"excerpt":{"rendered":"