[백준] 1699번 제곱수의 합

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

📌 문제

📌 입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

 

📌 출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

 

---

📌 풀이 방식 

해결 방법은 찾는데 생각보다 오래 걸린 문제입니다 🥹

 

(1) 제곱수들의 배열을 만들기 

(2) 각 숫자 n 에 대해 가장 적은 제곱수의 합으로 표현하는 최소 개수를 구한다 

* 현재 숫자 n 보다 적은 제곱수 중에서 dp[n-제곱수] + 1 이 가장 적은 경우로 업데이트

(3) N 의 최소 제곱수 개수를 출력

 

---

📌 코드

N = int(input())

dp = [0 for _ in range(N + 1)]
squares = []

for n in range(1, N+1):
    if n ** 2 <= N:
        dp[n ** 2] = 1
        squares.append(n ** 2)
    
    if n <= 3:
        dp[n] = n
    elif dp[n] == 0:
        m = dp[n-1] + 1
        for square in squares:
            if square > n:
                break
            m = min(m, dp[n-square] + 1)

        dp[n] = m

print(dp[-1])