백준 [1699]: 제곱수의 합

📌 백준 [1699]: 제곱수의 합

🔗 문제 링크

---

문제 설명 📄

자연수 n이 주어졌을 때, 자연수들의 제곱수의 합으로 표현할 때 필요한 최소 개수를 구하시오.
예를 들어 n=7일 때, 4+1+1+1로 4개의 제곱수의 합으로 표현할 수 있고, 이는 최소값이다.

---

문제 접근 방식 💡

• 동적 프로그래밍(DP)을 활용하여 최소 제곱수 개수를 계산.
• dp[i]를 자연수 i를 제곱수의 합으로 표현할 때 필요한 최소 개수로 정의.
• 점화식:
  • dp[i] = min(dp[i], dp[i - j*j] + 1) (j*j <= i)
• 초기값:
  • dp[0] = 0.

---

Solution 💻

n = int(input())

dp = [float('inf')] * (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])

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n√n)
  • 외부 반복문은 n번, 내부 반복문은 최대 √n번 실행됨.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • DP 배열이 n+1 크기로 사용됨.