BOJ-10803 정사각형 만들기(증명)

https://www.acmicpc.net/problem/10803

10803번: 정사각형 만들기

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}$

가 성립함이 증명된다.