개발/algorithm

[백준 17626번] Four Squares - python

zzi_on2 2022. 2. 14. 21:02

문제 링크

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

 

17626번: Four Squares

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1

www.acmicpc.net

풀이 

- dp 문제

- dp[i] 는 i 의 최소 개수의 제곱수 합 

- n보다 작거나 같은 제곱수들 i에 대해 dp[n-i*i]의 최솟값 min_value 을 구한다. 

n의 최소 개수의 제곱수의 합은 선택된 제곱수 1  + n-i*i 의 최소 개수의 제곱수의 합 min_value 

import sys
input = sys.stdin.readline

n = int(input())

if n == 1 or n == 2:
  print(n)
else:
    
  INF = int(1e9)
  dp = [0] * (n+1)

  dp[1] = 1
  dp[2] = 2

  # n보다 작거나 같은 최대 제곱수 1 + n과 해당 제곱수의 차이의 dp 값 

  for i in range(3,n+1):
    
    min_value = INF
    num = 1
    # i보다 작거나 같은 최대 제곱수
    while num*num <= i:
      min_value = min(min_value, dp[i-num*num])
      num += 1 
    
    dp[i] = 1 + min_value

  print(dp[n])