[python] 백준 17626 Four Squares

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

17626번: Four Squares

 

문제 해결

n보다 작은 수의 제곱수의 개수를 연결하는 것이므로 dp를 이용하는 것이 좋겠다는 생각을 하게 된다.

시간제한이 0.5초이기 때문에 빡세다. (python3로는 계속 탈락... pypy3로 풀었는데 python3까지 최적화를 못시키겠다.)

1 = $1^{2}$ 이므로 dp[1] = 1 dp[0] = 0으로 고정한다.

2부터는 for문을 통해 알아갈 것이다. dp[i]를 구할 때 i에서 어느 제곱수를 뺀 dp의 값들 중 최솟값을 구한 후 +1(어느 제곱수) 을 해주면 그 값이 dp[i]가 된다.

 

CODE

import sys
import math
n = int(input())
INF = sys.maxsize
dp = [0,1]
for i in range(2,n+1):
    minValue = INF
    for j in range(1, int(math.sqrt(i))+1):
        minValue = min(minValue, dp[i-j**2])
    dp.append(minValue+1)
print(dp[n])