백준 / 제곱수의 합 / 1699번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 제곱수의 합 / 1699번 (실버 2단계)

문제 사이트: https://www.acmicpc.net/problem/1699

 

문제 설명

---

나의 풀이

import math


def min_square_sum(n):
    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        dp[i] = i  # 최악의 경우: 1^2로만 이루어진 경우
        for j in range(1, int(math.sqrt(i)) + 1):
            dp[i] = min(dp[i], dp[i - j * j] + 1)

    return dp[n]


def main():
    # 예시 실행
    n = int(input())
    print(min_square_sum(n))

if __name__=="__main__":
    main()

---

※ 알아야 할 것