[백준] 17626번 Four Squares _ Python

[초기 접근 방법]

1. dp[i] : 합이 i가 되는 제곱수들의 최소 갯수

 

2. 점화식

dp[n] = min(dp[n], dp[n-제곱수] + 1)

→ 제곱수가 n보다 작을 때까지 비교

 

 

[생각]

문제에서 원하는 "합이 i가 되는 제곱수들의 최소 갯수"를 dp로 정의하고 풀면 되는 문제였어서, 쉽게 풀었던 것 같다.

아.. 시간 제한이 0.5초 이길래 시간초과가 나올까 봐 상수 시간복잡도까지 구했었다

 

 

[코드]

# 풀이 시간 : 15분
# 시간복잡도 : O(N*sqrt(N)) → 1100만?
# 공간복잡도 : O(n^2)
# 참고 : -

# 점화식을 세우자.. ㅎㅎ
import math
import sys
input = sys.stdin.readline

N = int(input())

# dp[i] : 합이 i가 되는 제곱수들의 최소 갯수
    # 점화식
    # dp[n] = min(dp[n], dp[n-제곱수] + 1)
    # 제곱수가 n보다 작을 때까지 비교
dp = [float('inf') for _ in range(N+1)]

for i in range(int(math.sqrt(N))+1):
    dp[i*i] = 1

# 각 dp값 구하기
for i in range(1, N+1):
    for j in range(1, int(math.sqrt(i))+1):
        dp[i] = min(dp[i], dp[i-(j*j)] + 1)

print(dp[N])