"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", mo: "mo", mrow: "mrow", 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/2313", children: "문제 링크" }) }), "\n", _jsx(_components.h2, { children: "문제" }), "\n", _jsx(_components.p, { children: "보석 가게에 여러 가지의 보석이 진열되어 있다. 각각의 보석은 정수로 표현되는 가치가 있다. 때로는 저주받은 보석이 있기 때문에 가치가 음수가 될 수도 있다." }), "\n", _jsx(_components.p, { children: "보석들은 총 n개의 줄에 나열되어 있다. 이제 당신은 각각의 줄에서 몇 개의 보석을 구매하려 한다. 이때, 각 줄에서 보석을 구매할 때 연속적인 보석들을 구매해야 한다. 즉, 어느 한 줄에서 1, 2번 보석을 구매할 수도 있고, 2, 3번 보석을 구매할 수도 있지만, 1, 3번 보석을 구매할 수는 없다." }), "\n", _jsx(_components.p, { children: "구매하는 보석의 가치의 총 합이 최대가 되도록 보석을 구매하는 방법을 찾아내는 프로그램을 작성하시오." }), "\n", _jsx(_components.h2, { children: "입력" }), "\n", _jsx(_components.p, { children: "첫째 줄에 정수 n(1 <= n <= 1,000)이 주어진다. 다음 2xn개의 줄에는 n개의 줄에 나열된 보석들에 대한 정보가 주어진다. 먼저 각 줄에 나열된 보석의 개수 L(1 <= L <= 1,000)이 주어지고, 그 다음 줄에 L개의 정수들이 주어진다. 각 정수는 각 보석의 가치를 나타낸다. 보석의 가치는 절댓값이 10,000보다 작거나 같은 정수이다." }), "\n", _jsx(_components.h2, { children: "출력" }), "\n", _jsx(_components.p, { children: "첫째 줄에 보석의 가치의 총 합의 최댓값을 출력한다. 다음 n개의 줄에는, 줄에서 몇 번째 보석부터 몇 번째 보석까지를 구매했는지를 출력한다." }), "\n", _jsx(_components.p, { children: "만약 최대가 되는 경우가 여럿이면, 구매한 보석들의 총 개수가 최소가 되는 방법을 출력한다. 이와 같은 경우도 여럿이라면, 출력한 nx2개의 수들을 하나의 수열로 생각하여, 사전식으로 가장 앞에 오는 경우를 출력한다." }), "\n", _jsx(_components.h2, { children: "풀이" }), "\n", _jsxs(_components.p, { children: ["각 가게는 독립적이므로, 결국 매 수열마다 최대 부분 배열을 한 번씩 구하면 된다. 코드에서는 카데인 알고리즘 형태로 ", _jsx(_components.code, { children: "curSum" }), "을 유지하면서 최대 합 구간을 찾는다."] }), "\n", _jsx(_components.p, { children: "현재 누적합이 0 이하가 되면 새로 시작하는 편이 유리하므로 시작점을 현재 위치로 옮긴다. 최대 합이 갱신되면 구간을 바꾸고, 같은 합이면 길이가 더 짧은 구간을 선택한다." }), "\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: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " L" }), _jsx(_components.span, { style: { color: "#81A1C1" }, 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: " totalAnsSum" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " store" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1000" }), _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: "vector" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "pair" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ">" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " ansIdx" }), _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: "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: "#D8DEE9FF" }, children: "\tvector" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: " sum" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "L" }), _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: "\tsum" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "push_back" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "store" }), _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: "\tint" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " start " }), _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: "#D8DEE9FF" }, children: " end " }), _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: "#D8DEE9FF" }, children: " cur " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 0" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "\tlong" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " long" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " maxSum " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " store" }), _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: "#81A1C1" }, children: "\tlong" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " long" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " curSum " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " store" }), _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: "\tfor" }), _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: " 1" }), _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: "#D8DEE9FF" }, children: " L" }), _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: "\t\tif" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "curSum " }), _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: "#D8DEE9FF" }, children: "\t\t\tcurSum " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " store" }), _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: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "\t\t\tcur " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "\t\t}" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "\t\telse" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "\t\t\tcurSum " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+=" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " store" }), _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: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "\t\t}" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "\t\tif" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "curSum " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ">" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " maxSum" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " {" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " " })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "\t\t\tmaxSum " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " curSum" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "\t\t\tstart " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " cur" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "\t\t\tend " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "\t\t}" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "\t\telse" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " if" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "curSum " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "==" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " maxSum" }), _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: "\t\t\tint" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " len " }), _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: "#D8DEE9FF" }, children: " cur " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "\t\t\tint" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " min_len " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " end " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "-" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " start " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1" }), _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: "\t\t\tif" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "len " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " min_len" }), _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: "\t\t\t\tstart " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " cur" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "\t\t\t\tend " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " i" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "\t\t\t}" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "\t\t}" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "\t}" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "\ttotalAnsSum " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " maxSum" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: "\tansIdx" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "push_back" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#88C0D0" }, children: "make_pair" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "start " }), _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: "#D8DEE9FF" }, children: " end " }), _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: _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: "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: "\tios_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: "\tcin" }), _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: "\tcout" }), _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: "#81A1C1" }, children: "\tint" }), _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: "\tcin " }), _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: _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "\t" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "\tfor" }), _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: "#D8DEE9FF" }, children: " N" }), _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: "#D8DEE9FF" }, children: "\t\tcin " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ">>" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " L" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "\t\tfor" }), _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: "#D8DEE9FF" }, children: " L" }), _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: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "\t\t\tcin " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ">>" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " store" }), _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: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#88C0D0" }, children: "\t\tsolve" }), _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: "\t}" }) }), "\n", _jsx(_components.span, { "data-line": "", children: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "\tcout " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<<" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " totalAnsSum " }), _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", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "\tfor" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " (" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "auto" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " idx " }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ":" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " ansIdx" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "\t\tcout " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<<" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " idx" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "first" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " <<" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " \"" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: " \"" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: " <<" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " idx" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "." }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: "second" }), _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: " " }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#81A1C1" }, children: "\treturn" }), _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: "t" }), _jsx(_components.mi, { children: "o" }), _jsx(_components.mi, { children: "t" }), _jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "l" }), _jsx(_components.mi, { children: "L" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(total L)" })] }) }) }), _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 mathnormal", children: "t" }), _jsx(_components.span, { className: "mord mathnormal", children: "o" }), _jsx(_components.span, { className: "mord mathnormal", children: "t" }), _jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0197em" }, children: "l" }), _jsx(_components.span, { className: "mord mathnormal", children: "L" }), _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.mi, { children: "N" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(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: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "N" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] })] }), "\n"] }), "\n", _jsx(_components.h2, { children: "마무리" }), "\n", _jsx(_components.p, { children: "결국 가게마다 최대 부분 배열을 구하는 문제다. 같은 최대 합일 때 더 짧은 구간을 고르는 추가 조건만 놓치지 않으면 된다." }), "\n", _jsx(_components.p, { children: _jsx(_components.img, { src: "/generated/posts/algorithm/boj-2313/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 2313 - 보석 구매하기