백준 1699 파이썬

https://www.acmicpc.net/problem/1699풀이자연수 N이 주어졌을 때, N을 제곱수들의 합으로 표현하는 데에 필요한 최소 항의 수를 구하는 문제이다.예를 들어서 4 = 2 ^ 2 → 1개, 7 = 2 ^ 2 + 1 ^ 2 + 1 ^ 2 + 1 ^ 2 → 최소 4개D[i]를 i의 제곱수의 합으로 나타낼 수 있는 최소 항의 수라고 생각하고 문제를 푼다.점화식은 다음과 같다.D[i] = min(D[i], 1 + D[i - j ^ 2])if (i ** 0.5).is_integer(): D[i] = 1 continue자기 자신 하나의 제곱수로 표현 가능한 경우는 바로 1로 설정하고 넘어간다.D[i] = 1e9 # 초기값은 매우 큰 수j = 1while j * j i보다 작은 모..