[백준] 17626번: Four Squares

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

initial

Initially I just did the biggest square number that is closes to the given integer and subtracting it from n until n reaches 0. But that is not a guaranteed way to get min number of ways. We can do it either via DP or brute force

First we initialise a dp list where all squares will have value 1. Then, as we iter from 1 to n, if dp[i]==0, then we can use previous dp values to build upon this dp[i] value, specifically the previous dp value we would be using is the previous squares j*j that is less or equal to i.

So the logic is like
dp[i]=dp[i-j*j] + dp[j*j]

But if there already is a value in dp[i] that isnt 1, we take the minimum value.

solution (only works in pypy3)

dp = [0] + [0 for _ in range(50000)]
n = int(input())
k = 1

while k*k <= n:
    dp[k*k] = 1
    k += 1

for i in range(1, n + 1):
    if dp[i] == 1:
        continue
    j = 1
    while j*j <= i:
        if dp[i] != 0:
            dp[i] = min(dp[i], dp[j*j] + dp[i - j*j])
        else:
            dp[i] = dp[j*j] + dp[i - j*j]
        j+=1

print(dp[n])

brute force

https://velog.io/@sbkwon16/%EB%B0%B1%EC%A4%80-17626%EB%B2%88-Python

complexity

Let's analyze the time and space complexity of the provided code:

Time Complexity:

• The first while loop runs until k*k becomes greater than n. The number of iterations is approximately proportional to the square root of n. Therefore, the time complexity of this part is O(sqrt(n)).
• The outer for loop iterates from 1 to n, and the inner while loop iterates until j*j becomes greater than i. In the worst case, the inner while loop runs for each value of i, resulting in a time complexity of O(n * sqrt(n)).
• Combining both parts, the overall time complexity is O(n * sqrt(n)).

Space Complexity:

• The dp array is created with a size of 50001. Therefore, the space complexity is O(50001), which can be simplified to O(1) or constant since it's not dependent on the input size n.

In summary, the time complexity is O(n * sqrt(n)), and the space complexity is O(1) for the provided code.