백준 1699번 제곱수의 합

 

해당수보다 작은 가장큰 제곱수를 찾아서 뺀뒤에 그 수를 다시 제곱수를 빼고 하는 식으로 작성하면 될것같다만

이러면 탑다운이 되어버리므로 다시 생각을 해보자

 

1부터 n까지 증가시키면서 각수를 제곱수로 만드는 항의 최소개수를 저장시켜놓고 불러오면 되겠다.

 

import sys

n=int(sys.stdin.readline().rstrip())

numbers=[]
numbers.append(0)
v=[]
v.append(0)
for i in range(1,n+1):
    numbers.append(i)
    v.append(0)

v[1]=1
prev_max=1
for i in range(2,n+1):
    if i>=(prev_max**2):
        v[i]=v[i-(prev_max**2)]+1
        prev_max+=1
    else:
        v[i]=v[i-((prev_max-1)**2)]+1
print(v[n])

일단 이렇게 작성하고 제출해봤다

왜지??

 

100000의 경우 316^2+12^2이니까 2가 맞고

12의 경우 3이 나와야하는데 4가 나온다 이게 문제였다.

(4+4+4) vs (9+1+1+1)

 

1부터n까지 제곱수로 순회를 돌아보자

import sys

n=int(sys.stdin.readline().rstrip())

numbers=[]
numbers.append(0)
v=[]
v.append(0)
for i in range(1,n+1):
    numbers.append(i)
    v.append(0)

v[1]=1
prev_max=1
for i in range(2,n+1):
    min_value=i
    for j in range(1,i+1):
        if j**2>i:
            break
        min_value=min(min_value,v[i-j**2]+1)
    v[i]=min_value
print(v[n])

이러면 O(n√n)인가

n이 10^5니까 아슬아슬할거같은데 일단 내보자

와우...