https://www.acmicpc.net/problem/10803
10803번: 정사각형 만들기
두 변의 길이가 모두 양의 정수인 직사각형 모양의 종이가 주어져 있다. 이 종이를 칼로 여러 번 잘라서 모든 조각이 한 변의 길이가 양의 정수인 정사각형이 되도록 하고자 한다. 칼로 종이를
www.acmicpc.net
dp로 모든 n, m에 대하여 구하면 TLE를 받기에 뭔가의 조건으로 시간복잡도를 줄여야한다.
대부분의 풀이는
$WLOG \ n \leq m$ 에 대해 $ 3n \leq m$의 조건에 대하여 $dp[n][m] = dp[n][m-n] + 1$을 해주고 있다.
이렇게 타이트한 조건에 대해선 증명하지 못하였고 정당성에 대해서도 잘 모르겠다.
찾은 조건은 $m >= \frac{n^2}{3}$ 에 대하여 $dp[n][m] = dp[n][m-n] + 1$ 이다.
이를 증명해보겠다.
# Definition)
$f(n, m) :$ $min \ number \ of$ $squares \ required \ to $ $fill \ n \times m \ square $
# Proof)
$Lemma \ 1)$ $f(n, m) <= max(n, m)$
귀납적으로 보일 수 있다.
1) $n = 1 \ and \ m = 1$이라면 $f(n, m) = 1 <= 1 = max(n, m)$
2) $n = m$ $f(n, m) = 1 <= max(n, m)$
3) $1 \leq n \leq a$, $1 \leq m \leq b$에 대해 성립할때 $ n= a+1, m = b $에 대해서도 성립함을 보이자.
3-1) $a+1 < b$
3-1-i)$a+1 \mid b$
$f(n, m) = f(a+1, b) $ $\leq \frac{b}{a+1}$ $ \leq b $ $\leq max(a+1, b) = max(n, m)$
3-1-ii)$a+1 \not \mid b$
$b = (a+1) p + q$ 라 두자($0 \leq q < a+1$)
$f(n, m) = f(a+1, b)$ $ \leq p + f(q, a)$ $ \leq p + max(a, q)$ $ \leq a + q + p$ $ \leq (a+1)p + q = $ $b = max(n, m)$
3-2) $a+1 > b$
$f(n, m) = f(a+1, b)$ $\leq 1 + f(a-b+1, b)$ $\leq 1 + max(a-b+1, b)$ $\leq max(a-b+2, b+1)$ $\leq a+1 = \leq max(a+1, b)$
3-3) $a+1 =b$
$f(a+1, b) = 1 <= max(a+1, b)$
3-1, 3-2, 3-3 으로 부터 $1 \leq n \leq a$, $1 \leq m \leq b$에 대해 성립할때 $ n= a+1, m = b $에 대해서도 성립함이 보여지고 $f(1, 1) = 1 <= max(1, 1)$의 초기조건으로 본 명제가 성립함을 알 수 있다.
$Lemma \ 2)$ $f(n, n+m) <= f(n, m) + 1$
$n \times (n+m)$ 사각형은 $n \times m$과 $n \times n$ 사각형 두개로 분할이 가능하니 자명하게 만족한다.
$Lemma \ 3)$ $f(n, m) > f(n, m-n)$ $if \ m \geq \frac{n^2}{3}$
$m \geq \frac{n^2}{3}$ 라는 제약조건이 뜬금없다고 생각 할 수 있으니 저 조건까지 유도해보자.
1. $f(n, n+m)$의 최적해가 $n \times n$사각형을 포함하는 경우
최적해에 포함된 $n \times n$사각형 1개만을 제거하여 만들어지는 $n \times m$ 사각형도 $f(n, m)$의 최적해일 것이다.
따라서 $ f(n, n+m) = 1 + f(n, m) > f(n, m)$ 임은 자명하다.
2. $f(n, n+m)$의 최적해가 $n \times n$사각형을 포함하지 않는 경우
$f(n, n+m)$의 최적해에서 왼쪽 끝부터 $n \times (nk)$의 사각형의 윈도우를 잡고 해당 윈도우와 겹쳐있는
($S= \left\{ p \ \mid \ p \in window \ and \ p \in square \right\}$일때 $size(S) > 0$) 모든 사각형을 제거, $k$개의 $n \times n$의 사각형으로 채운다.
윈도우의 왼쪽 끝부터 오른쪽 끝까지 $n \times 1$ 단위로 몇개의 사각형이 제거 되는지 생각해보자.
$n \times 1$ 안에 포함된 사각형들의 한변의 길이를 $[ a_1, a_2 , \ldots , a_c]$ 라 하면
$\displaystyle \sum_{i=1}^{c}\frac{1}{a_1}$ 으로 표시 할 수 있다.
(예를 들어 $3 \times 3$ 사각형 1개에 대하여 내부의 $1 \times 1$ 사각형이 제거 되었을때 $\frac{1}{9}$개가 제거 된걸로 취급하여 계산하면 슬라이드가 사각형을 포함할시 정확히 1개로 세어진다.)
$\displaystyle \sum_{i=1}^{c}a_i$ $= \ n$으로부터
$\displaystyle \sum_{i=1}^{c}\frac{1}{a_1}$ $\geq$ $\displaystyle c(\prod_{i=1}^{c}\frac{1}{a_1})^{\frac{1}{c}}$
$\geq$ $\displaystyle c \times c(\sum_{i=1}^{c}a_1^2)$ $ = \frac{c^2}{n}$ $\geq \frac{4}{n}$
임을 알 수 있다. ( $c < 2$라면 1에 해당됨으로 모순이다)
이후, $k$개의 $n \times n$의 사각형으로 채운다면 제거된 사각형들중 window와 겹치지 않은 부분들만 메꿔주면 타일링이 완료된다. 이러한 $t$개의 사각형들(window와 겹치지 않은 부분들) 의 길이 정보를 다음과 같이 표기하자.
$\left\{ (vert_i, hor_i) \ \mid \ 1 \leq i \leq t \right\}$
$\displaystyle \sum_{i=1}^{t} f(vert_i, hor_i) $ $\leq \displaystyle \sum_{i=1}^{t} max(vert_i, hor_i)$ $\leq = n$
($\because \ Lemma \ 1$)
이 얻어진다.
따라서 이렇게 구성한 타일링에 대하여 사용된 총 타일의 수에 대해 다음과 같이 쓸 수 있다.
$f(n, m) - deleted\_tile + tiles\_to\_fill $ $\leq f(n, m) - \frac{4}{n} (nk)+ k + n$
여기서 다음의 조건
$f(n, m) - \frac{4}{n}(nk) + k + n < f(n, m)$ $\iff$ $k > \frac{n}{3}$
을 이용하여 위의 식을 다시 써보면 $k > \frac{n}{3}$일때
$f(n, m) - deleted\_tile + tiles\_to\_fill $ $\leq f(n, m) - \frac{4}{n} (nk)+ k + n$ $ < f(n,m)$
최적해보다 작게 만들 수 있게되어 모순이다.
고로, $m \geq nk \geq \frac{n^2}{3}$($\iff$ $k > \frac{n}{3}$) 인 경우, $f(n, n+m)$의 최적해는 $n \times n$사각형을 포함함을 알 수 있고 본 명제가 증명 된다.
최종적으로 $Lemma \ 2)$와 $Lemma \ 3)$으로부터 $f(n, m) = f(n, m-n) + 1$ $if \ m \geq \frac{n^2}{3}$
가 성립함이 증명된다.