17626 - Four Squares

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

17626번: Four Squares

 

 

- Dynamic Programming

 

import sys
input = sys.stdin.readline

def isint(x):
    return not (x-int(x))

n = int(input())

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

k = [1]
for i in range(2, n+1):
    if isint(i**0.5):
        dp[i] = 1
        k.append(int(i**0.5))
        continue

    
    dp[i] = min([dp[i-(x**2)] for x in range(int((i//2)**0.5), k[-1]+1)]) + 1

print(dp[n])

 

동전 거스름돈 문제 중에 배수로 주어지지 않는 경우에, 주어진 동전 값을 뺀 dp 중 최소를 비교하는게 있는데 그 문제랑 비슷해서 dp식 구현은 그렇게 어렵지 않았다

 

근데 python3으로 제출하니까 시간 초과가 떠서.. pypy3로 제출하니 정답이 떴다