[Baekjoon] 17626번: Four Squares

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

17626번: Four Squares

 

문제 설명

라그랑주에 의하면 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명 되었습니다.

 

예를 들어서 3은 $3 = 1^2 + 1^2 + 1^2$ 으로 나타낼 수 있습니다. 3을 입력하면 항이 $1^2$ 3개이므로 (제곱수가 3개이므로) 출력값은 3입니다.

 

7은 $7 = 2^2 + 1^2 + 1^2$ 으로 나타내집니다. 7을 입력하면 항이 3개이므로 출력값은 3입니다.

 

이런식으로 N을 입력했을때 넷 혹은 그 이하의 제곱수로 표현하는 제곱수들의 최소 갯수를 출력하는 문제입니다.

 

우선 본 문제는 DP, 브루투포스에 분류되어 있는 문제로 아래와 같이 그리디 알고리즘을 생각해서 풀면 틀립니다.

 

"제곱수 들의 최소 합이라고 했으니깐 N을 넘지 않는 가장 큰 수의 제곱으로 덜어내면 되지 않을까?"

Ex) $12 => 3^2 + 1^2 + 1^2 + 1^2 $

위 생각대로 풀면 12에 대한 출력은 4입니다만 실제로 12를 만드는 제곱수들의 최소 갯수는

$12 = 2^2 + 2^2 + 2^2$ 로 출력은 3입니다. 반례가 존재하므로 이런 방법은 안되겠습니다.

 

결론적으로 DP로 풀어야 한다는 문제인데.. DP 문제 정말 어렵습니다 ㅠㅠ 아이디어도 잘 떠오르지 않구요..

짜증나지만 solved.ac 에 분류되어 있는 문제중에 3번째로 많은게 DP입니다.. 코테에서 DP를 포기한다는 것도 좀 그렇겠죠..?

 

일단은 한번 풀어봅시다.

 

 

소스코드 & 설명

우선 dp라는 배열에서 N이라는 숫자에 대한 연산의 최소 값을 dp[N] 에 저장하겠습니다.

우리가 목표하는 값은 dp[N] 에 값을 완성하고, 출력하는 것 입니다.

* 예를 들어서 1이라는 숫자에 대한 최소 연산의 값은 dp[1] 의 값입니다.

 

항상 DP문제를 풀던대로 N을 1~N까지 쭉 나열해보면서 이전 항과 다음 항의 관계에 대해 알아보겠습니다.

 

우선 1~4 까진 그냥 손으로 구해줍니다.

 

일단 4까지 나열해보면서 한가지 알 수 있는건 완전 제곱수의 경우에는 무조건 $(어떤 수)^2$ 으로 나타내질 것이기 때문에 무조건 1입니다.

 

5부터는 dp[5]의 값을 만들때는 dp[1] + dp[4] , dp[2] + dp[3], dp[3]+ dp[2], dp[4]+dp[1] 으로 만드는 경우의 수가 있습니다. 여기서 min() 으로 최소 값을 뽑아내면 dp[5]의 값을 완성해낼 수 있습니다.

 

특징을 보시면 항을 구성하는 두개의 인덱스를 더하면 N값이 나옵니다.

1+4 = 5, 2+3 = 5, 3 + 2 = 5 4 + 1 = 5 (N = 5)

 

dp[6]의 경우에도 dp[1] + dp[5], dp[2] + dp[4]... 와 같은 방법으로 만들어 낼 수 있습니다.

 

즉 dp[N]을 구하기 위해선 dp[N] 을 만들 수 있는 모든 경우의 수를 보고 min() 으로 최소값을 구해내면 될 거 같았습니다.

 

처음에 접근한 방법은 탐색을 할 때 브루투포스와 같은 방법으로

dp[N] 을 만들 수 있는 모든 수를 탐색해보았습니다.

 

 

 

 

for문 2개를 중첩시켜서 각 N마다 모든 경우의 수를 봐서 min() 으로 최소값을 구해봤는데 값은 제대로 나오나 우선 본 문제 시간 제한이 0.5초이고, $O^{n^2}$ 의 성능이기 때문에 34567와 같은 큰 값을 입력하면 정말 끔찍한 속도가 나왔습니다...

 

파이썬, C++로 해봤는데 C++은 좀 나았는데 파이썬은 돌려보니깐 프로그램이 멈춘줄 알았습니다 ㅋㅋ

조금더 성능을 개선할 방법이 필요할 거 같습니다.

 

아이디어가 떠오르지 않아서 인터넷 풀이를 보니 제곱수에 대한 이야기가 나와 있어서 생각이 떠올랐습니다.

"본 문제에서 완전 제곱수의 출력은 무조건 1이다." 

 

생각해보면 탐색을 할 때 전부 볼 필요 없이 제곱수만 따지면 제곱수는 값이 1이니깐 최소 값이 나올 수 있다는 기대를 해볼 수 있습니다.

 

dp[5] 를 탐색할때도 전부 볼 것이 아니라 dp[1^2] + dp[4] 와 dp[2^2] + dp[1] 만을 따지면 됩니다.

왜냐면 dp[1] 과 dp[4]는 어떤수의 제곱으로 나타내지는 완전제곱수기 때문에 값이 무조건 1입니다.

 

그래서 결론적으로는 N이라는 숫자보다 작은 완전 제곱수를 반복을 돌려서 탐색하면서 보면 됩니다.

그리고 dp[N]을 채우기 전에 N이 완전 제곱수인지 검사하고 완전 제곱수면 1로 채우고, 아니면 이전 항을 보면서 계산하면 되겠습니다.

 

제곱수만을 따져 12를 구하는 방법

 

#Four Squares 시간 미초과
n = int(input())

dp = [4] * (n+1) #0번째 인덱스는 편의를 위해 사용하지 않는다. (그리고 최대 4임.)
dp[1] = 1

#완전 제곱수 확인
def check_pfsq(n):
    return int(n ** 0.5) ** 2 == n

for i in range(2, n+1): #2~n
    if check_pfsq(i):
        dp[i] = 1
    else:
        j = 1
        while(j ** 2 < i):
            dp[i] = min(dp[j** 2] + dp[i - j**2], dp[i])
            j += 1
print(dp[n])

파이썬으로 완성한 코드입니다.

먼저 완전 제곱수인지 확인하고 아니면 1부터 자신 보다 더 작은 제곱수를 모두 보면서 dp항을 완성합니다.

 

일단 제곱수만 본다 하더라도 반복문이 2개 중첩되어 있어서 속도는 그다지 빠르지 못합니다.

파이썬 자체도 빠른건 아니니 사실 처음에 통과 여부가 의심됬습니다 ㅎㅎ.

 

제출해보니 python 3로는 시간 초과로 통과하지 못하고 pypy3는 통과하네요.

제출할 때 pypy3로 제출하면 될 거 같습니다.

 

여담

DP 어렵다.. ㅜ ㅜ

여러번 해도 항상 머리가 깨짐..