문제

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

풀이

• 숫자 n이 주어졌을 때 n을 최소 개수의 제곱수 합으로 표현

처음 문제를 접했을 때는 배열에 제곱수의 합을 모두 저장해 값을 하나씩 떼어 와서 결과값에 더해준 후 결과가 나오면 사용한 숫자의 개수를 반환하려고 했습니다.
그러나 이렇게 하면 너무 시간이 오래 걸려 비효율적이라 판단하여 코드를 작성하다 말았습니다.
다른 생각이 나질 않아 구글링을 해보았고 다른 사람들의 풀이를 보니 최소 제곱수 개수를 저장하는 방식이 좋아보여 참고해 문제를 풀어냈습니다.

dp[i]에 숫자 i를 제곱수 합으로 나타낼 때 필요한 최소 제곱 개수를 저장하는 방식을 이용했습니다.

ex) 숫자 12를 계산할 때

• 1^2 = 1, dp[12] == dp[12-1^2] + 1 즉, dp[11] + 1
  마찬가지로
• 2^2 = 4, dp[12] == dp[8] + 1
• 3^2 = 9, dp[12] == dp[3] + 1

이 중 최소 값을 찾으면 됩니다.

코드

# pypy3
import sys
input = sys.stdin.readline

n = int(input())
dp = [n] * (n+1)
dp[0] = 0

for i in range(1, n+1):
    j = 1
    while j*j <= i:
        dp[i] = min(dp[i], dp[i-j*j] + 1)
        j += 1

print(dp[n])