Math/Proof of PS solutions

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

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}$ 에 대하..