[백준] 17626번 Four Squares _ Python

https://www.acmicpc.net/problem/17626

 

[초기 접근 방법]

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

 

 

 

[생각]

dp[n]를 문제에서 정의해줘서 쉬운 문제였다.

점화식 또한 쉽게 생각할 수 있는 로직이여서 금방 풀었던 것 같다..

 

아.. 입력 범위 끝인 '50000'을 넣었는데 1-2초? 정도 걸리길래 시간초과 뜨나 해서

시간복잡도 상수 계산까지 했던.. 에피소드가 있다;;

 

 

 

[코드]

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

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)]

# 제곱수들의 dp 값을 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])