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

🥚문제

---

🥚입력/출력

---

🍳코드

PyPy3로 통과

import math
import sys
input = sys.stdin.readline

n = int(input().strip())
dp = [0]*(n+1)
# 제곱수에는 1을 미리 표시
k = 1
while k*k <= n:
    dp[k*k] = 1
    k += 1

for i in range(1, n+1):
    # i가 제곱수이면 skip
    if dp[i] == 1:
        continue

    min_value = 10**6
    j = 1
    while j*j <= i:
        min_value = min(min_value, dp[i-j*j] + 1)
        j += 1
    dp[i] = min_value

print(dp[n])

---

🧂아이디어

DP

• [백준 1699] 제곱수의 합 ❗ 문제와 같은 방식으로 풀이했다

• dp[x] : 자연수 x를 제곱수의 합으로 표현할 때 그 항의 최소 개수를 저장

• x가 이미 제곱수일 때 (x = y*y (1 <= y < x) )
  • x를 제곱수의 합으로 표현했을 때 x = y^2이므로 항이 1개
  • 따라서 이미 제곱수인 x들(1, 4, 9, ...)에 대해 dp[x] = 1로 초기화 해준다

• x가 제곱수가 아닐 때 (2, 3, 5, 6, 7, 8, 10, 11, ...)
  • 우리의 목표는 항의 개수를 최소로 만드는 것이기 때문에 dp에 저장된 값이 "1"인 제곱수들을 활용하여 식을 만들어낼 것이다.
  • y*y <= x 인 모든 제곱수, y*y에 대하여
  • 1 + dp[x-y*y] (= dp[y*y] + dp[x - y*y] )를 한 값 중 최소값을 dp[x]에 저장한다.