[17626] Four Squares in python

 

 

> dp

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

17626번: Four Squares

 

 

총 4개 이하의 자연수 제곱수들의 합으로

모든 자연수를 정의내릴 수 있다.

 

N = a^2 + b^2 + c^2 + d^2

 

 

dp를 푸는 문제는

항상 규칙이 존재한다.

 

 

n이 6일때를 생각해보자.

i가 1일땐 1이라고 초기화 진행

 

 

 

i=2일때,

2는 1의 제곱수들의 합으로 정의할 수 있음.

2 = 1^2 + 1^2

 

2 - 1^2 = 1이다.

따라서 dp[1]과 +1을 더해줌.

 

아래 그림에서는 0으로 표기되어 있으나.

최솟값을 구하려면 INF가 쓰여져있여야 함. (잘못 기재함)

 

 

i=3일때,

3 = 1^2 + 1^2 + 1^2이다.

dp[3-1^2] = dp[2] => 2를 이루고 있는 제곱수들의 개수에다가

+1을 해준다 -> 3-2하면 1이 남으니까 1^2의 값은 항상 1

 

 

i=4일때,

4=2^2

dp[4-2^2]=dp[0]=0+1=1

 

 

 

i=5일때,

5=2^2+1^2

dp[5-2^2]=dp[1]+1

= dp[1]+1

 

 

 

i=6일때,

6=2^2+1^2+1^2

dp[6-2^2]=dp[2]=2+1=3

 

 

N보다 작거나 같은 제곱수들중에

가장 큰 제곱수를 선택하여 

N에서 그 값을 빼준다.

 

그리고 해당 값의 위치에 있는 dp값에 +1을 더해준다.

+1을 해주는 이유는

N에서 가장 큰 제곱수를 빼주게 되면

가장 큰 제곱수의 개수는 포함되지 않는 상태가 되어버리기 때문이다.

 

 

i가 6일때를 보면

6에서 4를 빼주면 2가 된다.

이때의 2는 6=2^2+1^2+1^2

파란색으로 색칠해둔 부분에 있는 제곱수의 최소의 개수이다.

 

그리고 남아있는 가장 큰 제곱수의 개수 +1을 더해줘야

6의 제곱수들의 개수를 구할 수 있게 되는 것!

import sys

n = int(sys.stdin.readline())
dp = [0 for _ in range(n + 1)]
dp[1] = 1
for i in range(2, n + 1):
    j = 1
    temp = 1e9
    while j ** 2 <= i:
        temp = min(temp, dp[i - j ** 2])
        j += 1
    dp[i] += temp + 1
print(dp[n])