아카이브

BOJ 10803 — 정사각형 만들기: 점화식 경계의 증명

이전 아카이브에서 보존한 기술 글: BOJ 10803 — 정사각형 만들기: 점화식 경계의 증명.

· PS · baekjoon · Math · 알고리즘 · BOJ 10803 · 동적 계획법 · 기하 · 증명
이 글의 목차

BOJ 10803 — 정사각형 만들기

문제 모델과 주장

유효한 절단 계획은 길로틴 방식 분할이다. 즉, 절단할 때마다 직사각형 하나를 두 직사각형으로 나누고, 마지막 조각은 변의 길이가 양의 정수인 정사각형이어야 한다. f(n,m)f(n,m)을 n×mn\times m 직사각형을 분할하는 데 필요한 정사각형의 최소 개수라고 하자. 회전할 수 있으므로 f(n,m)=f(m,n)f(n,m)=f(m,n)이다.

원문은 m≥n2/3m\ge n^2/3일 때 f(n,m)=f(n,m−n)+1f(n,m)=f(n,m-n)+1이라고 주장한다. 하지만 원문의 증명은 mm과 n+mn+m 사이에서 변수를 바꾸면서 조건을 함께 옮기지 않았다. 아래에서는 더 보수적인 충분조건을 증명한다.

m−n≥n23⟹f(n,m)=f(n,m−n)+1,m-n\ge \frac{n^2}{3}\quad\Longrightarrow\quad f(n,m)=f(n,m-n)+1,

여기서 n,mn,m은 양의 정수이고 n≤mn\le m이다. 이 글은 원문의 더 약한 임계값을 주장하지 않는다.

나머지 직사각형의 상계

양의 정수 a,ba,b에 대해

f(a,b)≤max⁡(a,b)f(a,b)\le \max(a,b)

이다. 대칭성에 의해 a≤ba\le b라고 하자. a=1a=1이면 단위 정사각형 bb개로 분할한다. a≥2a\ge2이면 b=qa+sb=qa+s, q≥1q\ge1, 0≤s<a0\le s<a로 쓴다. s=0s=0이면 a×aa\times a 정사각형 qq개면 충분하다. s>0s>0이면 먼저 a×aa\times a 정사각형 qq개를 두고 남은 a×sa\times s 직사각형을 분할한다. 긴 변에 대한 강한 귀납법과 대칭성으로 f(s,a)≤af(s,a)\le a이므로

f(a,b)≤q+a≤qa+s=b.f(a,b)\le q+a\le qa+s=b.

마지막 부등식은 b−(q+a)=(q−1)(a−1)+(s−1)≥0b-(q+a)=(q-1)(a-1)+(s-1)\ge0에서 따른다. 이 구성은 모두 길로틴 방식 절단으로 만들 수 있다.

점화식 경계의 증명

r=m−nr=m-n이라 두고 r≥n2/3r\ge n^2/3이라 하자. n×(n+r)n\times(n+r) 직사각형을 n×nn\times n 정사각형 하나와 n×rn\times r 직사각형으로 나눌 수 있으므로

f(n,n+r)≤f(n,r)+1.(1)f(n,n+r)\le f(n,r)+1. \tag{1}

반대 방향의 엄격한 부등식을 보이자. F=f(n,n+r)F=f(n,n+r)라 하고 최적 길로틴 분할을 하나 고정한다.

분할에 n×nn\times n 정사각형이 있으면 그 정사각형은 전체 높이를 차지한다. 이를 제거하면 왼쪽과 오른쪽에 길로틴 방식으로 분할된 직사각형이 남고, 두 너비의 합은 rr이다. 두 분할을 나란히 놓으면 F−1F-1개의 정사각형으로 n×rn\times r을 분할할 수 있으므로 f(n,r)≤F−1f(n,r)\le F-1이다.

이제 최적 분할에 n×nn\times n 정사각형이 없다고 가정하자. 다음과 같이 놓는다.

q=⌊n3⌋+1.q=\left\lfloor\frac n3\right\rfloor+1.

그러면 q>n/3q>n/3이고 nq≤n+n2/3≤n+rnq\le n+n^2/3\le n+r이다. 왼쪽에서 너비가 nqnq인 띠 WW를 잡는다. 정수 변의 정사각형으로 이루어진 정수 직사각형의 길로틴 분할에서 모든 경계 좌표는 정수이므로, WW는 너비 1인 열 nqnq개로 나뉜다.

각 열에서 그 열을 가로지르는 정사각형들의 변 길이를 s1,…,sc<ns_1,\ldots,s_c<n이라 하자. 이 정사각형들의 세로 구간은 전체 높이 nn을 분할하며, n×nn\times n 정사각형이 없으므로 c≥2c\ge2이다. 코시–슈바르츠 부등식에 의해

∑i=1c1si≥c2∑isi=c2n≥4n.\sum_{i=1}^c\frac1{s_i}\ge \frac{c^2}{\sum_i s_i}=\frac{c^2}{n}\ge\frac4n.

변이 ss인 정사각형 하나가 가로지르는 단위 열마다 1/s1/s개로 세면 전체 기여량은 최소 4q4q이다. 변이 ss인 정사각형은 WW의 단위 열을 최대 ss개 가로지르므로 전체 기여량이 s/s=1s/s=1을 넘지 않는다. 따라서 WW와 교차하는 원래 정사각형은 적어도 4q4q개다. 그 개수를 DD라 하면 D≥4qD\ge4q이다.

WW와 교차하는 정사각형 DD개를 제거하고, WW를 n×nn\times n 정사각형 qq개로 채운다. 오른쪽 영역은 WW의 세로 경계에서 원래 길로틴 분할을 잘라 얻는다. 분할 트리를 따라 귀납하면 이 잘라낸 분할도 길로틴 구조를 유지한다. 경계선의 왼쪽에 완전히 있는 하위 트리는 버리고 오른쪽에 완전히 있는 하위 트리는 그대로 둔다. 교차하는 수직 분할 노드에서 경계선이 절단선보다 왼쪽이면 왼쪽 자식을 잘라 오른쪽 자식과 함께 유지한다. 경계선이 절단선 이후라면 왼쪽 자식을 버리고 오른쪽 자식을 자른다. 수평 분할 노드에서는 두 자식을 모두 자르고 수평 절단을 유지한다. 따라서 경계선을 가로지르는 정사각형만 직사각형 조각으로 남는다. 각 조각의 높이는 ss, 너비는 ss 이하이다. 조각들의 세로 구간은 서로 겹치지 않으므로 높이의 합은 nn 이하이다. 앞의 상계를 적용하면 이 조각들을 채우는 데 정사각형이 모두 합해 최대 nn개 필요하다. 그 밖의 오른쪽 정사각형은 그대로 둔다.

이렇게 만든 전체 분할의 정사각형 수는 최대 F−D+q+nF-D+q+n이다. 새로 놓은 정사각형 중 가장 왼쪽의 하나를 제거하면 너비가 rr인 직사각형이 남고, 정사각형 수는 최대

F−D+q+n−1≤F−3q+n−1<FF-D+q+n-1\le F-3q+n-1<F

이다. D≥4qD\ge4q이고 q>n/3q>n/3이기 때문이다. 따라서 이 경우에도 f(n,r)<Ff(n,r)<F이다.

결국 f(n,n+r)>f(n,r)f(n,n+r)>f(n,r)이다. 두 값은 정수이므로 (1)과 합치면

f(n,n+r)=f(n,r)+1f(n,n+r)=f(n,r)+1

을 얻는다. r=m−nr=m-n을 대입하면 주장한 경계가 증명된다.

적용 범위

이 임계값은 충분조건이지 필요조건이 아니다. 원문에서 제시한 임계값보다 보수적이며, 이 증명으로 원문의 더 강한 조건을 사용할 수는 없다. 증명은 직사각형을 재귀적으로 자르는 길로틴 모델을 전제로 한다.

출처

2022-05-31에 0archlinux0 / MINJUN PARK이 게시하고 CC BY 4.0으로 표시한 Tistory 52번 글을 바탕으로 한다. 이 버전은 변수와 임계값의 이동을 바로잡고 타일 수 계산을 명시하며, 여기서 증명한 충분조건만 제시한다.

참고