백준 17626 Four Squares python

Concept

특정 수를 최소한의 제곱수로 표현한다

Trial. 1

임의의 수 n을 해당 수의 제곱근의 정수값을 제곱한 값의 테이블 값 + 1로 풀 수 있을거라 생각했다

점화식

dp[n] = dp[n - int(√n) ^ 2] + 1 

Error Trial. 1

n의 값이 43라고 가정하자
'시도 1' 의 점화식대로라면 43 = 6^2 + dp[7]이다
여기서 dp[7]의 값은 2^2 + 1 + 1 + 1로 4이다
즉 '시도 1'대로라면 dp[43] = 1 + 4 = 5가 나오게 된다

그러나!

만약 43에서 5^2를 먼저 뺀다면
43 = 5^2 + 4^2 + 1^2 + 1^2로 나타낼 수 있다
즉 Trial 1은 오류가 있다

Trial. 2

시도 1이 dp만을 사용했다면 시도 2는 여기서 brute force를 추가한다

점화식

(1 <= i <= n)
dp[n] = min(dp[n - int(√i) ^ 2)) + 1

코드

import math

n = int(input())

dp = [int(1e9) for _ in range(50001)]
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3
for _ in range(4, n + 1):
    d = int(math.sqrt(_))
    for _n in range(1, d + 1):
        dp[_] = min(dp[_], 1 + dp[_ - _n ** 2])

print(dp[n])

여담

시간초과 걸릴 줄 알았다. 하지만 생각해보니 O(n) = n * √n이고 n이 50000이라 0.5초 안에 충분히 풀 수 있는 문제였다