[백준] 1699번 문제 (제곱수의 합) 파이썬(Python) 풀이

import sys

n = int(input())
dp = [0] * 100001
dp[1], dp[2], dp[3], dp[4] = 1, 2, 3, 1

for i in range(5, n + 1):
    if int(i ** 0.5) ** 2 == i:
        dp[i] = 1
    else:
        if dp[i - 1] + dp[1] == 2:
            dp[i] = 2
        else:
            left, right = 1, i - 1
            count = sys.maxsize
            while left < right:
                count = min(count, dp[left] + dp[right])
                left += 1
                right -= 1
            dp[i] = count

print(dp[n])

나의 풀이는 이렇다. 사실 Python3 컴파일러로는 시간초과가 나길래 PyPy3로 제출했는데 가까스로 풀렸다. 다른 사람들의 풀이를 보니 이런식으로 풀지는 않았다. 시간 효율도 좋고 공간 효율도 내 코드보다 좋다. 따라서 딱히 이 풀이를 추천하지는 않지만 좀 더 직관적으로 이해하기는 쉬울거라 생각한다.

 

우선 dp에 해당 제곱수 항의 최소개수를 담아두고 점진적으로 최소 항의 개수를 구한다.

for 문에서 해당 숫자가 완전 제곱수이면 해당 숫자의 최소 항의 개수는 당연히 1 이니 dp[i] = 1을 해주고,

그게 아니라면 left, right 포인터로 점진적으로 숫자를 비교해가며 최소 항의 개수를 찾는다.