📚 1699 - 제곱수의 합

제곱수의 합

문제 이해

• 이 문제에서는 n보다 작은 것 중에 제곱 수의 최댓값을 기준으로 소스를 작성하려 했지만

➡️ 12인경우 : 9와 3 : 4 , 8와 4 : 3이 된다.
➡️ dp[12] = 3

• 위 예시와 같이 반례가 존재한다.
• n까지 반복문을 돌리면서 1 ~ n 사이에 있는 제곱수 를 찾고 검사를 한다. (소스를 보면 이해가 쉬울 것이다.)

나의 소스

n = int(input())

dp = []

for idx in range(n + 1):
    dp.append(idx)

for i in range(2, n+ 1):
    for j in range(2, i+1):
        if j * j > i:
            break
        else:
            dp[i] = min(dp[i], dp[i - j * j] + 1)

print(dp[n])

참고한 소스

# 참고하여 수정한 코드

n = int(input())

dp = [0] * (n + 1)

for i in range(1, n+ 1):
    dp[i] = i
    j = 1

    while j * j <= i:
        dp[i] = min(dp[i], dp[i - j * j] + 1)
        j += 1

print(dp[n])

시간 복잡도