[Python] 17626. Four Squares

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

17626번: Four Squares

 

접근법

• n을 제곱수의 합으로 표현하되, 가장 최소 개수를 찾는 문제이다.

# pypy로만 성공
def main():
    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:
            temp = n_list[i - (j ** 2)]
            min_v = min(min_v, temp)
            j += 1
        n_list[i] = min_v + 1
    print(n_list[n])

if __name__=="__main__":
    main()

---

사용된 알고리즘

다이나믹 프로그래밍, 브루트포스 알고리즘