I was going through the following question

Given a paper of size A x B. Task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.

I tried writing a dp and a greedy solution for this problem, but none of them worked. Unfortunately the site from where I am practising this question also does not have a correct solution. Can someone please suggest a solution to this problem or is this also NP-hard like polygon partition ?

Complete Problem Statement

Read about euclid gcd algorithm for details.

Repeat this until B!=0:

Ans += A/B

A, B = B, A%B

Try to prove how. Just see, that i try to make squares of size B, A/B is number of squares i am able to make, and last line counts number of suares required to cover area, which couldnt be covered in squares of side B.

This approach is not optimal for all cases

you are right… Its not optimal

example

30 35

can be decomposed into

20*20 + 15*15 + 15*15 + 10*10 + 10*10

for calculating result of

30 35

can we calculate result for

6 7 ?

will it give same results ??

Oh

My mistake.

Some sort of DP solution must be there.

1 Like