[백준] 17626번 (python 파이썬)

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:
        tmp = n_list[i - (j**2)] + 1
        min_v = min(min_v, tmp)
        j += 1
    
    n_list[i] = min_v 

print(n_list[n])

1 = 1^2
2 = 1^2 + 1^2
3 = 1^2 + 1^2 + 1^2
4 = 2^2
5 = 2^2 + 1^2
6 = 2^2 + 1^2 + 1^2
7 = 2^2 + 1^2 + 1^2 + 1^2
8 = 2^2 + 2^2
9 = 3^2
10 = 3^2 + 1^2
11 = 3^2 + 1^2 + 1^2
12 = 3^2 + 1^2 + 1^2 + 1^2
13 = 3^2 + 2^2
14 = 3^2 + 2^2 + 1^2

 

어떠한 규칙이 있을것 같아서 일일이 써봤다

혼자 찾아낸 것은 n 이하의 가장큰 자연수가 무조건 포함된다는 것이다

이후에는 뭘 해야될지 몰랐다

 

다른 블로그 참고해서 보니까

현재 인덱스 - 제곱수 + 1로 풀었다 (여기서 +1은 제곱수를 따로 더하는 것이다)

 

무조건 가장 큰 제곱수로 빼지 않아도 최소가 나올 수 있다는 것을 빼먹지 말자

지금 구하는 최솟값이 제곱수의 최소 개수이므로!!

 

문제 구해야 되는 것을 간과하지 말자