[Baekjoon 1699] 제곱수의 합

문제 1699

N = int(input())
dp = [i for i in range(N+1)] # 모든 수는 1의 제곱수로 표현 가능
for i in range(1,N+1):
    for j in range(1,i):
        if j*j > i :
            break

		# dp[i] 보다 작은 제곱수의 합이 존재하면
        if dp[i] > dp[i-j*j] + 1 :
            dp[i] = dp[i-j*j] + 1
            
print(dp[-1])

풀이

d[0] = 0
d[1] = 1
d[2] = 2
d[3] = 3
d[4] = d[4-2*2] + 1
d[5] = d[5-2*2] + 1

...

d[9] = d[9-3*3] + 1
d[10] = d[10-3*3] + 1

...

틀린 코드

import math

N = int(input())
answer=0

# N==0이면 종료
while N:
	# 4보다 작은 제곱수는 1 뿐
    if N < 4:
        answer+=N
        break
    
    # N - N이 가질 수 있는 가장 큰 제곱수의 값이 0 이상이면 answer++
    x = int(math.sqrt(N))
    # print(f'x: {x}')
    if N-x**2 >= 0:
        N-=x**2
        answer+=1
        
print(answer)

결과