[백준-17626] Four Squares / Python

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

17626번: Four Squares

n = int(input())
d = [0] * (n + 1)
d[0], d[1] = 0, 1

for i in range(2, n + 1):
    minValue = 1e9
    j = 1
    while (j ** 2) <= i:
        minValue = min(minValue, d[i - (j ** 2)])
        j += 1
    d[i] = minValue + 1

print(d[n])

 

해설

DP 문제였다. 문제에서 사용되는 규칙을 바로 찾지 못해 꽤나 애를 먹었다..😰

구글링을 통해 문제에 사용되는 규칙을 찾았는데 이 규칙을 알고나니 코드 구현은 딱히 어렵지 않았다.

 

규칙은 다음과 같다.

- n보다 작거나 같은 제곱수를 찾고 n-제곱수를 인덱스로 가진 값에 1을 더해주면 된다.

 >> d[i - (j**2)] + 1

 

모든 DP 문제에서 사용되는 규칙들을 빠르게 찾아내야 하는데.. 연습이 더 필요하다!😂