"use strict"; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const {useMDXComponents: _provideComponents} = arguments[0]; function _createMdxContent(props) { const _components = { a: "a", annotation: "annotation", code: "code", figure: "figure", h2: "h2", img: "img", li: "li", math: "math", mi: "mi", mn: "mn", mo: "mo", mrow: "mrow", msub: "msub", mtext: "mtext", p: "p", pre: "pre", semantics: "semantics", span: "span", ul: "ul", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsx(_components.p, { children: _jsx(_components.a, { href: "https://www.acmicpc.net/problem/11444", children: "문제 링크" }) }), "\n", _jsx(_components.h2, { children: "문제" }), "\n", _jsx(_components.p, { children: "피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다." }), "\n", _jsxs(_components.p, { children: ["이를 식으로 써보면 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "F" }), _jsx(_components.mi, { children: "n" })] }), _jsx(_components.mo, { children: "=" }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "F" }), _jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" })] })] }), _jsx(_components.mo, { children: "+" }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "F" }), _jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "2" })] })] }), _jsx(_components.mtext, { children: " " }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "≥" }), _jsx(_components.mn, { children: "2" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "F_n = F_{n-1} + F_{n-2}\\ (n \\ge 2)" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.8333em", verticalAlign: "-0.15em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "F" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.1514em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "-0.1389em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.8917em", verticalAlign: "-0.2083em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "F" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3011em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "-0.1389em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsxs(_components.span, { className: "mord mtight", children: [_jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mbin mtight", children: "−" }), _jsx(_components.span, { className: "mord mtight", children: "1" })] }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.2083em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "F" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3011em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "-0.1389em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsxs(_components.span, { className: "mord mtight", children: [_jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mbin mtight", children: "−" }), _jsx(_components.span, { className: "mord mtight", children: "2" })] }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.2083em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mspace", children: " " }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≥" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] }), "가 된다."] }), "\n", _jsxs(_components.p, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "17" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n=17" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "17" })] })] })] }), "일 때까지 피보나치 수를 써보면 다음과 같다."] }), "\n", _jsx(_components.p, { children: "0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597" }), "\n", _jsx(_components.p, { children: "n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오." }), "\n", _jsx(_components.h2, { children: "입력" }), "\n", _jsx(_components.p, { children: "첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다." }), "\n", _jsx(_components.h2, { children: "출력" }), "\n", _jsx(_components.p, { children: "첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다." }), "\n", _jsx(_components.h2, { children: "풀이" }), "\n", _jsxs(_components.p, { children: ["피보나치 수는 선형 점화식이라서 행렬 거듭제곱으로 빠르게 구할 수 있다. ", _jsx(_components.code, { children: "[[1, 1], [1, 0]]" }), " 행렬의 거듭제곱을 이용하면 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "n" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" })] }) })] }), "번째 피보나치 수를 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(\\log n)" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), "에 계산할 수 있다."] }), "\n", _jsx(_components.p, { children: "코드에서는 빠른 거듭제곱처럼 지수를 절반으로 줄여 가며 행렬을 제곱한다. 짝수 지수는 절반 결과를 두 번 곱하고, 홀수 지수는 한 번 더 기본 행렬을 곱하면 된다." }), "\n", _jsx(_components.p, { children: "점화식을 행렬 형태로 바꿔 빠르게 압축하는 문제다." }), "\n", _jsx(_components.h2, { children: "코드" }), "\n", _jsx(_components.figure, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.pre, { style: { backgroundColor: "#2e3440ff", color: "#d8dee9ff" }, tabIndex: "0", "data-language": "cpp", "data-theme": "nord", children: _jsxs(_components.code, { "data-language": "cpp", "data-theme": "nord", style: { display: "grid" }, children: [_jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#5E81AC", fontWeight: "bold" }, children: "#" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "include" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " <" }), _jsx(_components.span, { style: { color: "#A3BE8C" }, children: "iostream" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ">" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#5E81AC", fontWeight: "bold" }, children: "#" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "include" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " <" }), _jsx(_components.span, { style: { color: "#A3BE8C" }, children: "vector" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ">" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "using" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " namespace" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " std" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "typedef" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " vector" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "vector" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ">" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " matrix" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "const" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " long" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " long" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " MAXN " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1000000007" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#616E88" }, children: "//행렬 곱" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "matrix " }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "matrixMultiply" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "matrix" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "&" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " a" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " matrix" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "&" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " b" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " matrix " }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "result" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "2" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " vector" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "<" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "long" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " long" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ">(" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "2" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "))" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " for" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 2" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "++" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " for" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " j " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " j " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 2" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " j" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "++" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " for" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " k " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " k " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 2" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " k" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "++" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " result" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "i" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "][" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "j" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " +=" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "a" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "i" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "][" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "k" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " *" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " b" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "k" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "][" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "j" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "])" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " %" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " MAXN" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " result" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "i" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "][" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "j" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " %=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " MAXN" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " return" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " result" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "}" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#616E88" }, children: "//행렬 A의 거듭제곱" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "void" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " matrixPower" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "matrix" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "&" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " A" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " matrix" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "&" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " result" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " long" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " long" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " n" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " while" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "n " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ">" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "n " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "%" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 2" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " result " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " matrixMultiply" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "result" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " A" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " A " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " matrixMultiply" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "A" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " A" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " n " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "/=" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 2" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "}" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "long" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " long" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " fibonacci" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "long" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " long" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " n" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "n " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 2" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " return" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " " }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " matrix A " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {{" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "}," }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "}}" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " matrix result " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {{" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "}," }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "0" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "}}" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#88C0D0" }, children: " matrixPower" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "A" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " result" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " n " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "-" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " return" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " result" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "0" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "][" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "0" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " %" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " MAXN" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "}" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "void" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " solve" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "()" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " long" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " long" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " n" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " cin " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ">>" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " n" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " cout " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<<" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " fibonacci" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "n" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " <<" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " '" }), _jsx(_components.span, { style: { color: "#EBCB8B" }, children: "\\n" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "'" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "}" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " main" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "()" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " ios_base" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "::" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "sync_with_stdio" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "false" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " cin" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "tie" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "NULL" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: " cout" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "tie" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "NULL" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#88C0D0" }, children: " solve" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "()" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: " return" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "}" }) })] }) }) }), "\n", _jsx(_components.h2, { children: "복잡도" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["시간 복잡도: ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" }), _jsx(_components.mi, { children: "N" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(\\log N)" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "N" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] })] }), "\n", _jsxs(_components.li, { children: ["공간 복잡도: 상수 크기 행렬 기준 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(1)" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] })] }), "\n"] }), "\n", _jsx(_components.h2, { children: "마무리" }), "\n", _jsx(_components.p, { children: "피보나치를 그대로 반복 계산할 필요는 없다. 점화식을 행렬로 바꾸면 큰 N도 빠른 거듭제곱으로 처리할 수 있다." }), "\n", _jsx(_components.p, { children: _jsx(_components.img, { src: "/generated/posts/algorithm/boj-11444/assets/1.png", alt: "" }) })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent };

BOJ 11444 - 피보나치 수 6