[백준] 1699 제곱수의 합 <부제: 너무 느린 파이썬 극복하기;;>

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

1699번: 제곱수의 합

 

 

최종적으로 맞은 코드는 다음과 같다. 

우선 이중 for문을 쓸 때 j의 범위를 1부터 i에 루트를 씌운 값까지!!! 라는 범위를 주어 반복문의 범위를 줄여서 시간초과를 극복했다,,

또 이번에 새롭게 알게된 점은 

i**2 보다 i*i 가 계산 속도가 더 빠르다는 것이다 !!!!! 헐 ~~~~~~ 찾아보니까 i**2 는 몇 제곱을 하는지 옵션을 줄 수 있어서 , 단순하게 자기자신을 두번 곱하는 i*i 보다, 기능이 더 많아서 더 느리다고 한다. 

이런 사소한 하나하나도 파이썬은 신경써주어야 한다 ㄱ- 난 코테 언어로 파이썬이 다른 언어보다 간결해보인다고 생각해서 선택했으나.

이렇게 시간초과에 관해 되게 예민한 언어이므로 ㅠㅠ 앞으로도 기억해두어야 겠다 

import math

n = int(input())
INF = int(1e9)
dp = [INF]*(n+1)
dp[0] = 0
dp[1] = 1

for i in range(2, n+1):
    for j in range(1, int(math.sqrt(i))+1):
        temp = i
        total = 0
        if j**2 <= i:
            count = i // (j*j)
            temp -= (j*j) * count
            total = count + dp[temp]
            if dp[i] > total:
                dp[i] = total

print(dp[n])