[백준][Python] 17626번 Four Squares

17626번: Four Squares

 

코드

n = int(input())
n_list = [0]*(n+1)
n_list[1] = 1
for i in range(2,n+1):
    j = 1
    min_v = 4
    while((j**2)<=i):
        a = n_list[i-(j**2)]
        min_v = min(min_v,a)
        j+=1
    n_list[i] = min_v+1    
print(n_list[n])

 

설명

규칙이 뭔지 모르겠어서 구글링을 해봤다. 

규칙은 n - (n보다 작거나 같은 제곱수) 를 인덱스로 갖는 값에 1을 더해주면 된다. 

문제에서 제곱수의 최대 개수가 4라고 했으므로 min_v 값을 4로 두고 더 작은 값이 존재하면 그 값으로 바꿔줬다.