[BOJ] 제곱수의 합


  • BOJ의 제곱수 문제 풀이입니다

문제 풀이

  • 숫자를 제곱수로 표현할 때 가장 적은 수로 표현하는 방법을 찾는 문제입니다

  • 이 문제는 Dynamic Programming 문제로 문제를 작게 쪼개서 해결할 수 있습니다

  • 각 숫자는 다음과 같은 방식으로 진행되는데, 해당 숫자 보다는 작으면서 1이 아닌수로 제곱수로도 나타낼 수 있는 경우에 가장 적은 항으로 숫자를 표현할 수 있습니다

  • 1 - 1^2
  • 2 - 1^2 + 1^2
  • 3 - 1^2 + 1^2 + 1^2
  • 4 - 2^2
  • 5 - 2^2 + 1^1
  • 6 - 2^2 + 1^1 + 1^1

  • 문제의 예시처럼 11=3^2+1^2+1^2 또는 11=2^2+2^2+1^2+1^2+1^2 로도 나타낼 수 있기 때문에 어떠한 숫자를 써서 나타냈을 때 가장 적은 항으로 나타낼 수 있는지 비교를 해줍니다

전체 코드

import sys
import math

N = int(sys.stdin.readline())

dp = [0] * (N+1)

for i in range(1, N+1):
    dp[i] = i # 1^2로 나타내는 경우
    for j in range(1, math.floor(math.sqrt(i))+1 ):
        if dp[i] > dp[i-j*j]+1:
            dp[i] = dp[i-j*j]+1

print(dp[N])


Reference









© 2020. by dkmqflx

Powered by dkmqflx