종이 최소 갯수의 정사각형 조각으로 자르기

13 * 29  : 13*13 2개, 3*3 4개 1* 1 3개 = ans : 9

풀이 : 아무래도 짧은 변을 한 변으로 하는 정사각형을 긴 쪽으로 할 수 있는 만큼 만든 후에, 남은 길이를 재귀적으로 호출하면 된다.

base case는 한쪽 길이가 1이면 조각의 수는 긴 쪽 길이이다.

int findsquares(int M, int N){

// base case

if(N==1) return M;

// general case

int count = M/N;

return count + findsquares(N,M%N);

}

시간 복잡도 .. O(log 루트N) 쯤 되지 않을까? 작은 것 보다 작게 만드니까 작은 것으로 만든다고 가정하면 대략 logN이고..