[백준 17626] Four Squares

문제

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

17626번: Four Squares

---

아이디어1 - DP

Pypy3에서는 성공했고, Python에서는 시간 초과가 발생한 방법이다. 

 

아이디어는 다음과 같다. 

자연수 n에 대하여, n을 최소 개수의 제곱수 합으로 표현했을 때 그 개수를 f(n)이라고 하자.

 

이 때, n보다 작은 모든 제곱수 k에 대해 m = n - k 라고 하면,

f(n)은 f(m)의 최솟값 + 1이 된다. (제곱수를 더한다는 것은 +1만 하면 되는 것이기 때문.)

 

무슨 말이냐면, n = 11 이라고 해보자. n = 3^2 + 1^2 + 1^2 이기 때문에 f(n) = 3이다. 

이 때, 11보다 작은 제곱수는 1, 4, 9가 있다.

11에서 제곱수를 빼서 얻을 수 있는 m은 10, 7, 2가 된다. 그러면 f(m)는 2, 4, 2가 되고, 이 중 최솟값은 2이기 때문에 최솟값인 2에 1을 더해주면 된다.

• 이 때, m = 7인 경우가 최적의 경우가 아닌 이유를 알아보자.
  • 11 = 7 + 4 로 분해하는 경우가 그 경우인데, 애초에 7을 만들기 위해서 필요한 제곱수가 이미 4개나 된다.
  • 7 = 2^2 + 1^1 + 1^1 + 1^1 이므로 f(7) = 4 가 된다.
  • 그러면  11 = 2^2 + 1^1 + 1^1 + 1^1 + 2^2 로 표현하면 5개나 필요하다.
• 반면에  m = 10, 2가 최적의 경우가 되는 이유를 알아보자.
  • 11 = 10 + 1 또는 11 = 2 + 9 두 가지가 그 예시인데 첫 번째 예시만 보자.
  • 10 = 3^2 + 1^1 이므로 f(10) = 2 가 된다.
  • 그러면 11 = 3^2 + 1^1 + 1^1 으로 표현하면 3개만 있으면 된다. 

 

이 과정을 DP를 이용해서 구현할 수 있다. 위에서 구한 최적의 경우를 예로 들어보자.

첫 번째 예시의 경우) [11 = 10 + 1]	첫 번째 예시의 경우) [11 = 2 + 9]
f(11) = f(10) + 1 f(10) = f(1) + 1 f(1) = 1	f(11) = f(2) + 1 f(2) = f(1) + 1 f(1) = 1

그러면 dp라는 1부터 n까지 순회하면서, n을 이용해서 m을 구하고, f(m)의 최솟값에 1을 더한 값을 f(n)으로 넣어준다.

이 때, dp[n] = f(n)이 된다. 

 

그리고 dp[n]을 계산하면 된다. 

그런데, 파이썬에서는 시간 초과가 발생하고 Pypy3에서만 성공한다. 

 

n이 커지면 DP가 비효율적일 수 있다.

n = 48400인 경우를 생각해보자. 48400 = 220^2이기 때문에 f(n)이 1이다.

그래도,  어쨌든 dp[48400]까지 연산을 해야 한다. 

---

아이디어2 - Brute-force 성공

그렇다면 49729가 223의 제곱이라는 걸 알면, 한 번의 연산으로 f(49729) = 1이라는 걸 보일 수 있지 않을까?

• 단순히 루트를 취해서 정수인지 아닌지만 확인하면 된다.
• n이 이미 제곱수이면 한 번의 연산만 해도 충분하다는 뜻이다. 

그게 아니라 만약 n이 48401이면 f(48401) = f(48400) + 1이라는 것만 알면 f(48401) = 2라는 걸 보일 수 있지 않을까?

• 이 말은 f(n) = 2. 즉, n이 제곱수 + 제곱수인 경우를 의미한다. 
• n에서 제곱수를 뺐을 때 제곱수가 되면 된다. 
• 이 경우라면, (n - 1^1) ~ (n - 223^2) 까지 223번의 연산이면 끝난다. 

f(n) = 3이면, (n - 제곱수 - 제곱수)가 제곱수가 되면 된다. 

• 이 경우는 최대 223^2번의 연산을 해야하지만, 리스트에서 조건에 맞는 값을 추출해서 최소값을 비교하는 연산과 다르게 (n - 제곱수 - 제곱수)를 계산해서 정수인지만 확인하는 단순한 연산이기 때문에 시간 복잡도에서 손해를 볼 일이 없으며, 운이 .

이 모든 경우를 만족하지 않으면 4가 된다.

---

Solution1

import math

n = int(input())
dp = [0, 1]
 
for i in range(2, n+1) : 
    bound = int(math.sqrt(i))+1
    best = min([dp[i-j**2] for j in range(1, bound)])
    dp.append(best+1)
print(dp[-1])

---

Solution2

import math

n = int(input())

def check(n) :
    sqrt = math.sqrt(n)

    if sqrt.is_integer() : 
        return 1
    
    for i in range(1, int(sqrt)+1) : 
        if math.sqrt(n-i**2).is_integer() :
            return 2
        
    for i in range(1, int(sqrt)+1) : 
        for j in range(1, int(sqrt)+1) : 
            val = n - i**2 - j**2
            if val > 0 : 
                if math.sqrt(val).is_integer() : 
                    return 3
    
    return 4

print(check(n))