[백준 1699번] 파이썬 - 제곱수의 합

백준 1699번

시간 제한 2초, 메모리 제한 128MB

# 조건

• 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다.
• 예를 들어 11=32+12+12(3개 항)이다.
• 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다.
• 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다.
• 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.
• 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 자연수 N이 주어진다. (1<=N<=100,000)

출력

• 주어진 자연수를 제곱수의 합으로 나타날 때에 그 제곱수 항의 최소 개수를 출력한다.

# 접근 방법

• dp를 이용해서 풀어준다.
• 우선 각 숫자의 크기로 dp값을 초기화 해준다 => 1로 만들었을 떄 제곱항의 개수
• 그 다음 1부터 N까지 범위의 반복문과 1부터 i까지의 반복문을 2중 반복문으로 돌려준다.
• 현재 수가 7인 경우, 1부터 6까지를 순회하는 것인데 이 때, dp[7]이 dp[7-2^2] + 1보다 크다면, 현재 기록된 7을 표현하는 제곱항의 개수가 최소가 아니었으므로 갱신해준다.
• 따라서, j * j가 i보다 커지면 break해주고 다음 수로 넘어간다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N = int(input())
dp = [x for x in range(N + 1)]
for i in range(1, N + 1) :
    for j in range(1, i) :
        if j* j > i:
break
if dp[i] > dp[i - j * j] + 1:
dp[i] = dp[i - j * j] + 1
print(dp[N])