[Python] 17626 Four Squares

문제 바로 가기

문제 설명

• 알고리즘 : DP
• 제곱 반복 수행 -> 문제 답 저장 후 해당 부분이 필요한 경우 저장된 결과를 사용 -> DP로 풀 수 있다는 것을 알 수 있다.
• 단순하게 구현으로 이중 for문으로 구현할수있지만, 이 문제는 시간제한 0.5초로 파이썬이 1초에 100000000 연산이 가능하다 가정했을때, 이문제는 최악의n의 경우가 50000*50000=2500000000 으로 풀수 없다.
• 로직의 핵심은 자신의 수에서 그보다 작은 수의 제곱수를 뺀 것의 최소를 구하고 거기에 한개를 더해주면 된다.
• 점화식을 구하기 어려울 땐 , 직접 그림을 그려 규칙을 찾아보자!
• 참고! Python으로 시간초과가 나와 PyPy로 해야된다!!

점화식 도출

직접 표를 그려봤습니다
. 위에 그림에서 사다리같이 생긴 표는 dp 배열이고, j는 제곱수입니다.
예를들어 5는 자기보다 작은 제곱수들중 가장 큰 제곱수는 2 입니다
그래서 2의 제곱 +1이므로 dp[5]=2이다

13의 예시를 보면, 자기보다 작은 제곱수중 가장 큰 제곱수는 3이다
그래서 13-(3의 제곱=9)=4
dp[4]+dp[9]가 dp[13]의 최소값이 됩니다!

• 점화식

min_value = min(min_value, dp[i - (j**2)])

전체 코드

import sys
input=sys.stdin.readline
N = int(input())
dp = [0,1]

for i in range(2, N+1):
    min_value = 1e9
    j = 1

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

    dp.append(min_value + 1)
print(dp[N])