Loading...
Loading...
Loading...
A floor of area n is covered with square tiles whose side is a whole number, so their areas are 1, 4, 9, 16 and so on. Print the fewest tiles whose areas add up to exactly n.
Example 1
Input
12
Output
3
4 + 4 + 4 uses three tiles.
Example 2
Input
13
Output
2
4 + 9 uses two tiles.
Try the problem first. Open one hint at a time.
This is coin change where the coins are the square numbers up to n.
dp[a] is one square plus the best for a minus that square.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor