BOJ 17626 - Four Squares #1

최근에 풀었던 전형적인 DP 유형 중에 하나를 골라봤다.

비슷한 문제는 동전 문제가 있다.

 

이러한 유형의 풀이 전략은

가장 작은 수를 시작으로 개수를 만들고

점점 수를 증가하면서 최소 갯수를 구하는 식으로 누적하면 된다.

또한 각 제곱의 값은 배열(혹은 리스트)에 미리 계산해 놓으면 속도를 조금 더 빠르게 할 수 있다.

 

작성한 소스는 아래와 같다.

n = int(input())
dp = [i for i in range(50001)]
l = int(50000**0.5) + 1
s = [i*i for i in range(l+1)]

for j in range(2, l):
    for i in range(s[j], n+1):
        if i - s[j] < 0 :
            break
        dp[i] = min(dp[i-s[j]]+1, dp[i])

print(dp[n])

그런데 시간초과가 난다..

시간 복잡도의 최대는 50000 * (50000**0.5) = 11180 k라서 1억 개까지는 안돼서 괜찮을 거 같은데..

python 자체에 list 접근 시간이 오래걸리는건가..?

 

다른 방법을 찾아봐야 할 듯싶다.

일단 오늘은 여기까지.