[python] 17636. Four Squares

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

 

 

풀이

 

이번 문제는 제곱수의 합을 구하는 문제입니다.

dp로 해결했는데, 점화식을 찾는 것이 쉽지 않았습니다. 

 

 

이해를 위해 그림을 첨부했습니다. 

i를 가지고 j를 만든다고 할 때, 그림처럼 항의 개수를 가지게 됩니다.

 

이는 제곱수일 때 +1만큼 커지게 됩니다. (그림을 보고 이해하시면 되겠습니다 !)

 

브루트포스로도 문제를 해결할 수 있습니다.

주석과 함께 코드를 첨부해두겠습니다.

 

 

 

- DP 문제 풀이

N = int(input())
dp = [n for n in range(N+1)]

for i in range(2, int(N**0.5)+1):
    for j in range(i*i, N+1):
        dp[j] = min(dp[j], dp[j-i*i]+1)

print(dp[N])

 

 

 

- 브루트포스 문제 풀이

n = int(input())
arr = [0 if i**0.5%1 else 1 for i in range(n+1)] # 제곱수는 1로 저장

min_ = 4
for i in range(int(n**0.5), 0, -1):
    if arr[n]: # n이 제곱수인 경우
        min_ = 1
        break
    elif arr[n-i*i]: # 나머지가 제곱수인 경우
        min_ = 2
        break
    else:
        for j in range(int(n-i*i)**0.5, 0, -1):
            if arr[(n-i*i)-j**2]: # 제곱수를 한번 더 뺀 나머지가 제곱수일 경우
                min_ = 3
print(min_)