"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", msup: "msup", ol: "ol", p: "p", pre: "pre", semantics: "semantics", span: "span", table: "table", tbody: "tbody", td: "td", th: "th", thead: "thead", tr: "tr", ul: "ul", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsx(_components.p, { children: _jsx(_components.a, { href: "https://www.acmicpc.net/problem/10836", children: "문제 링크" }) }), "\n", _jsx(_components.h2, { children: "문제" }), "\n", _jsx(_components.p, { children: "크기가 MxM인 격자 형태의 벌집이 있다. 이 벌집의 각 칸에는 여왕벌이 될 애벌레들이 한 마리씩 자라고 있다." }), "\n", _jsx(_components.p, { children: "격자칸의 좌표계를 다음과 같이 설정한다. 제일 왼쪽 위 칸의 좌표는 (0,0)이다. 그 아래쪽 칸들의 좌표는 순서대로 (1,0), (2,0), ...등이다. 좌표가 (i,0)인 칸의 오른쪽 칸들의 좌표는 순서대로 (i, 1), (i,2), ... 등이다." }), "\n", _jsx(_components.p, { children: "애벌레들은 매일 에너지를 모아서 정오(낮 12시) 에 한번 자라는데, 여기에 걸리는 시간은 매우 짧아서 무시할 수 있다. 첫날 아침 모든 애벌레들의 크기는 1이고, 이러한 과정을 N일 동안 반복한다." }), "\n", _jsx(_components.p, { children: "각 애벌레가 자라서 크기가 커지는 정도는 하루에 +0, +1, +2의 세 가지 중 하나이다. 더하기(+) 기호는 앞으로 생략한다. 구체적으로 각 애벌레가 자라는 정도를 결정하는 규칙은 다음과 같다." }), "\n", _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "제일 왼쪽 열과, 제일 위쪽 행의 애벌레들은 자신이 자라는 정도를 스스로 결정한다. 이들은 입력으로 주어질 것이다. 애벌레들이 자라는 정도를 왼쪽 제일 아래 칸에서 시작하여 위쪽으로 가면서 읽고, 제일 위쪽 칸에 도착하면 오른쪽으로 가면서 행의 끝까지 읽었다고 하자. 모든 입력에서 이렇게 읽은 값들은 감소하지 않는 형태이다." }), "\n", _jsx(_components.li, { children: "나머지 애벌레들은 자신의 왼쪽(L), 왼쪽 위(D), 위쪽(U)의 애벌레들이 다 자란 다음, 그 날 가장 많이 자란 애벌레가 자란 만큼 자신도 자란다." }), "\n"] }), "\n", _jsx(_components.p, { children: "M = 4, N = 2인 예를 하나 들어보자. 다음은 각 격자에 있는 애벌레의 첫날 아침의 크기이다." }), "\n", _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { children: "1" }), _jsx(_components.th, { children: "1" }), _jsx(_components.th, { children: "1" }), _jsx(_components.th, { children: "1" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: "1" }), _jsx(_components.td, { children: "1" }), _jsx(_components.td, { children: "1" }), _jsx(_components.td, { children: "1" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "1" }), _jsx(_components.td, { children: "1" }), _jsx(_components.td, { children: "1" }), _jsx(_components.td, { children: "1" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "1" }), _jsx(_components.td, { children: "1" }), _jsx(_components.td, { children: "1" }), _jsx(_components.td, { children: "1" })] })] })] }), "\n", _jsx(_components.p, { children: "2일 동안 제일 왼쪽 열과 제일 위쪽 행에 있는 7마리의 애벌레들이 자라는 정도를 왼쪽 제일 아래칸에서 시작하여 위쪽으로 가면서 읽고, 제일 위쪽 칸에 도착하면 오른쪽으로 가면서 행의 끝까지 읽었을 때, 다음과 같다고 하자." }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "1일: 0, 0, 1, 1, 1, 2, 2" }), "\n", _jsx(_components.li, { children: "2일: 1, 1, 1, 1, 1, 1, 2" }), "\n"] }), "\n", _jsx(_components.p, { children: "첫날 저녁에 애벌레들은 아래와 같은 크기를 가진다. 예를 들어, 좌표 (1,1)의 애벌레는 왼쪽 애벌레의 크기가 1만큼 자랐고, 왼쪽 위의 애벌레가 1만큼 자랐고, 위쪽 애벌레도 1만큼 자랐으므로, 자신도 1만큼을 자란다. 또, 좌표 (3,3)의 애벌레는 규칙을 따르면 2만큼 자람을 알 수 있다." }), "\n", _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { children: "2" }), _jsx(_components.th, { children: "2" }), _jsx(_components.th, { children: "3" }), _jsx(_components.th, { children: "3" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: "2" }), _jsx(_components.td, { children: "2" }), _jsx(_components.td, { children: "3" }), _jsx(_components.td, { children: "3" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "1" }), _jsx(_components.td, { children: "2" }), _jsx(_components.td, { children: "3" }), _jsx(_components.td, { children: "3" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "1" }), _jsx(_components.td, { children: "2" }), _jsx(_components.td, { children: "3" }), _jsx(_components.td, { children: "3" })] })] })] }), "\n", _jsx(_components.p, { children: "둘째 날이 지났을 때는 동일한 과정에 따라 다음과 같이 됨을 확인할 수 있다." }), "\n", _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { children: "3" }), _jsx(_components.th, { children: "3" }), _jsx(_components.th, { children: "4" }), _jsx(_components.th, { children: "5" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: "3" }), _jsx(_components.td, { children: "3" }), _jsx(_components.td, { children: "4" }), _jsx(_components.td, { children: "5" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "2" }), _jsx(_components.td, { children: "3" }), _jsx(_components.td, { children: "4" }), _jsx(_components.td, { children: "5" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "2" }), _jsx(_components.td, { children: "3" }), _jsx(_components.td, { children: "4" }), _jsx(_components.td, { children: "5" })] })] })] }), "\n", _jsx(_components.p, { children: "격자칸의 크기, 날자 수, 날자별 제일 왼쪽 열과 제일 위쪽 행의 애벌레들이 자라는 정도를 입력으로 받아 마지막 날 저녁의 애벌레들의 크기를 출력하는 프로그램을 작성하라" }), "\n", _jsx(_components.h2, { children: "입력" }), "\n", _jsx(_components.p, { children: "입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 <= M <= 700)과 날짜 수 N(1 <= N <= 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 줄에는 첫날부터 순서대로 제일 왼쪽 열과 제일 위쪽 행의 애벌레들이 자라는 정도가 다음의 형식으로 주어진다. 본문에서 보인 것과 같이, 자라는 크기를 제일 왼쪽 아래 칸에서 시작해서 위쪽으로 올라가서 제일 위쪽에 도착하면 오른쪽으로 이동하며 읽었다고 하자. 이 값들은 감소하지 않는다. 따라서, 이 수열을 처음부터 읽었을 때 0의 개수, 1의 개수, 2의 개수를 순서대로 입력에 준다. 하루에 대해서 이 세 개수들의 합은 2M-1임이 자명하다. 세 값들 중에 0이 있을 수 있다" }), "\n", _jsx(_components.h2, { children: "출력" }), "\n", _jsx(_components.p, { children: "M개의 줄에 각각 M개의 자연수를 출력한다. 이는 각 애벌레의 마지막 날 저녁의 크기를 첫 행부터, 각 행에서는 왼쪽부터 제시한 것이다. (본문의 예와 동일한 형태이다.)" }), "\n", _jsx(_components.h2, { children: "풀이" }), "\n", _jsx(_components.p, { children: "처음에는 2차원 배열 전체에 대해 누적합이나 시뮬레이션을 해야 할 것처럼 보이지만, 실제로는 가장자리 정보만 관리해도 충분하다." }), "\n", _jsxs(_components.p, { children: ["핵심은 내부 칸의 성장이 항상 왼쪽, 왼쪽 위, 위쪽 중 최댓값을 따라간다는 점이다. 그런데 입력으로 주어지는 가장자리 성장량은 ", _jsx(_components.code, { children: "0" }), ", ", _jsx(_components.code, { children: "1" }), ", ", _jsx(_components.code, { children: "2" }), "가 이 순서대로 등장하는 감소하지 않는 수열이다. 그래서 어떤 위치의 최댓값도 결국 위쪽 방향에서 전달되는 값으로 정리되고, 내부 전체를 따로 저장하지 않아도 맨왼쪽 열과 맨위쪽 행의 최종 성장량만 알면 전체 격자를 복원할 수 있다."] }), "\n", _jsxs(_components.p, { children: ["이를 위해 길이 ", _jsx(_components.code, { children: "2M - 1" }), "의 배열 하나를 두고, 왼쪽 아래에서 위로 올라간 뒤 맨 위 행을 오른쪽으로 가는 순서를 그대로 대응시킨다. 초기값은 모두 1이고, 매일 입력되는 ", _jsx(_components.code, { children: "zero" }), ", ", _jsx(_components.code, { children: "one" }), ", ", _jsx(_components.code, { children: "two" }), "를 이용해 증가량이 1인 구간과 2인 구간만 더해 주면 된다. 감소하지 않는 수열이기 때문에 실제 성장값 전체를 읽지 않고도 구간 업데이트처럼 처리할 수 있다."] }), "\n", _jsxs(_components.p, { children: ["최종 출력 단계에서는 이 배열의 앞 ", _jsx(_components.code, { children: "M" }), "개를 뒤집어 첫 열로 사용하고, 나머지 ", _jsx(_components.code, { children: "M - 1" }), "개를 각 행의 오른쪽 부분에 그대로 붙이면 마지막 벌집 상태를 만들 수 있다. 문제를 2차원 전체가 아니라 가장자리 성장 정보의 누적으로 바꿔 보는 것이 핵심이다."] }), "\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: "#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: " m" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _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: "#81A1C1" }, children: "int" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " sum" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: "1400" }), _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: "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: "#88C0D0" }, children: "\tfill" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "(" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "sum" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " sum " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "+" }), _jsx(_components.span, { style: { color: "#B48EAD" }, children: " 1400" }), _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", _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: " day " }), _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: " day " }), _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: " day" }), _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\tint" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " zero" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " one" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "," }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " two" }), _jsx(_components.span, { style: { color: "#81A1C1" }, 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: " zero " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ">>" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " one " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ">>" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " two" }), _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\tint" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " idx " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "=" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " zero" }), _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: " 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: " one" }), _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: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: "\t\t\tsum" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "idx" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "++" }), _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: "\t\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: " two" }), _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: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D8DEE9" }, children: "\t\t\tsum" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "idx" }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "++" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "]" }), _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: "\t}" }) }), "\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: "\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: " m" }), _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\tcout " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<<" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " sum" }), _jsx(_components.span, { style: { color: "#ECEFF4" }, children: "[" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: "m " }), _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: "#ECEFF4" }, children: "]" }), _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: ";" })] }), "\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: "#D8DEE9FF" }, children: " m" }), _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: " m " }), _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: " j" }), _jsx(_components.span, { style: { color: "#81A1C1" }, 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\tcout " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: "<<" }), _jsx(_components.span, { style: { color: "#D8DEE9" }, children: " sum" }), _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: "#ECEFF4" }, children: " \"" }), _jsx(_components.span, { style: { color: "#81A1C1" }, 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: "#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: "\t}" }) }), "\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: "#D8DEE9FF" }, children: "\tcin " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ">>" }), _jsx(_components.span, { style: { color: "#D8DEE9FF" }, children: " m " }), _jsx(_components.span, { style: { color: "#81A1C1" }, children: ">>" }), _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: "#88C0D0" }, children: "\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: "}" }) })] }) }) }), "\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: "N" }), _jsx(_components.mo, { children: "+" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "M" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(N + M^2)" })] }) }) }), _jsxs(_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: "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: "1.0641em", verticalAlign: "-0.25em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "M" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", 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 mtight", children: "2" }) })] }) }) }) }) })] }), _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: "M" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(M)" })] }) }) }), _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: "M" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] })] }), "\n"] }), "\n", _jsx(_components.h2, { children: "마무리" }), "\n", _jsxs(_components.p, { children: ["겉으로는 벌집 전체를 매일 갱신해야 할 것처럼 보이지만, 입력 수열의 단조성과 내부 칸의 전파 규칙을 합치면 가장자리만 추적해도 충분하다. 2차원 문제를 ", _jsx(_components.code, { children: "2M - 1" }), " 크기의 1차원 배열로 축소한 점이 이 풀이의 핵심이다."] }), "\n", _jsx(_components.p, { children: _jsx(_components.img, { src: "/generated/posts/algorithm/boj-10836/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 10836 - 여왕벌