BruteForce_10_Four Squares(17626)

문제

출력하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

풀이

• DP를 이용했다
• 최솟값을 담는 방법으로,,
• 제곱수로 구하는 법을 계속 누적한다.
• minV = min(minV, dp[i-(j**2)])
• 중요한 점은 j**2 가 구하려는 i 보다 작은 경우 !

코드

import sys
sys.stdin = open("input.txt", "rt")
input = sys.stdin.readline

n = int(input())
dp = [0,1]

for i in range(2,n+1):
    minVal = 1e9
    j = 1
    while(j**2) <= i:
        minVal = min(minVal, dp[i-(j**1)])
        j += 1
    dp.append(minVal)
print(dp[n])