[Python] 백준17626 Four Squares

18 Jan 2023 in Study on Algorithm

백준17626 Four Squares 링크

문제

예제 입력

---

코드

n = int(input())

dp = [0]*50001
dp[1] = 1

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1
    for j in range(2, int(i**0.5) + 1): # 2의 제곱, 3의 제곱 등...
        dp[i] = min(dp[i], dp[i - j**2] + 1)

print(dp[n])

설명

파이썬을 통해서 사용자로부터 입력받아 자료형 list를 사용하여 dp알고리즘으로 Four Squares를 구현했습니다.

---

결과