[백준] 17626 파이썬(python) : Four Squares - 상세해설

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

17626번: Four Squares

 

 

dp[n-(j**2)] +1 : 자신보다 작은 제곱수 중에 가장 큰 값을 뺀값을 인덱스로 가지는 dp테이블의 값에 1을 더한 것

 

import sys
import math
n = int(sys.stdin.readline())
dp = [0]*50001 #1
dp[1] = 1

if n == int(math.sqrt(n))**2: #2
    print(1)
else:
    for i in range(2, n+1):
        if i == int(math.sqrt(i))**2: #3
            dp[i] = 1
        else: #4
            l = []
            for j in range(1, math.floor(math.sqrt(i))+1): #5
                l.append(dp[i-(j**2)]+1) #6
            dp[i] = min(l)
    print(dp[n])

 

#1 : dp 테이블 최대갯수로 초기화

#2 : 입력값이 만일 제곱수라면 입력값을 만드는 제곱수의 개수는 1개이기에 1출력

#3 : 입력값이 제곱수가 아니어서 반복문을 돌릴때 (1은 dp값 초기화되어 있어서 2부터 돌림) 바텀업 방식으로 쌓아올리는 중 i가 제곱수라면 i를 만드는 제곱수의 개수는 1이기에 dp[i] = 1로 초기화

#4 : 바텀업으로 쌓아올리는 중 i가 제곱수가 아니라면

#5 : i의 제곱근의 정수부분까지 반복문 실행

#6 : 자신보다 작은 제곱수들 중 가장 큰값을 자신에서 빼고 그 값을 인덱스로 가지는 dp테이블의 값에 1을 더한다. 이렇게하면 #4에서 걸러진 제곱수가 아닌 i값들에 자신보다 작은 가장큰 제곱수를 찾아 뺴준값을 인덱스로 가지는 dp값은 이전까지의 값의 제곱수 개수를 포함하니까 +1 하면 자신의 제곱수 개수가 된다.

그런값들을 모두 더해주고 그중에서 가장 작은 값이 최종 dp[i]의 값이 된다.

 

#6이 설명이 길었는데 예시를 들면 다음과 같다.

#4에서 걸러진 제곱수가 아닌 수 24는 24 = 4² + 2² + 2²로 나타낼 수 있다. 즉 dp[24] = 3이다. 24인 부분 제곱수 4²는 16이고 dp[16]은 2가 된다. dp[16]=2에서 +1을 해서 dp[24]는 3이 되는것이다.