[백준 17626번] Four Squares (python)

문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

 

기록

(dp 2일차) 완전탐색 -> dp -> 내맘대로(?) 3가지 코드로 수행했다.

 

완전탐색은 for문을 3개 중첩시켜 가장 작은 제곱수의 합을 찾았다. 결과는 시간초과.

 

dp는 이후 구글링을 통해 찾은 코드인데, 0부터 n+1의 제곱수의 최소합을 dp 배열에 모두 저장하는 방법으로 진행된다. 모든 제곱수를 돌며 1+dp[n-제곱수]를 비교하여 최소 제곱수 합를 구해나가며, n의 최소 제곱수 합을 구하면 종료된다. 예를 들어 n이 10일 때, 1(1^2)+dp[10-1^2](9의 최소합), 1(2^2)+dp[10-2^2](6의최소합), 1(3^2)+dp[10-3^2](1의최소합) 이 3가지를 비교하여 가장 최솟값을 찾아내는 방법이다. 점화식처럼 표현하자면 dp[10]=1+min(dp[9], dp[6], dp[1]) 이렇게 되는 것이다. 결과는 python3로 하면 시간초과, pypy3로 하면 성공이 뜬다.

 

마지막으로 내가 푼 방법은 완전탐색에서 for문을 하나 줄인 형태이다. 바깥 for문은 제곱수+나머지를 비교하는데, n이 제곱수면 최소합은 1, 나머지도 제곱수면 최소합은 2가된다. 둘다 아니라면 중첩된 for문에서 위의 나머지를 제곱수+나머지로 나눠서 한 번 더 비교한다. 여기서 나머지가 제곱수이면 최소합은 3이되고 모두 아니라면 4가 된다. 이렇게 중첩된 for문을 돌면서 제곱수+나머지로 나눠 한 번 비교하고, 제곱수+(제곱수+나머지)로 나눠 두 번 비교하는 방법이다. 결과는 python3로 해도 성공:) 시간도 더 빨랐다!

 

 

코드

<dp>

import math

n = int(input())
dp = [0,1]

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

print(dp[n])

1. n까지 모든 수의 최소 제곱수의 합을 저장할 dp배열을 만든다.

2. 자신보다 작은 모든 제곱수의 1+dp[제곱수를 뺀 나머지] 값을 비교하여 최솟값을 찾아 저장한다.

3. n의 최소제곱수의 합을 출력한다.

 

<내가 푼 방법>

n = int(input())
sq = [0 if i**0.5%1 else 1 for i in range(n+1)] # 제곱수는 1로 저장

mincount = 4
for i in range(int(n**0.5), 0, -1):
    if sq[n] : # n이 제곱수일 경우
        mincount=1
        break
    elif sq[n-i**2] : # 나머지가 제곱수일 경우
        mincount=2
        break
    else:
        for j in range(int((n-i**2)**0.5), 0, -1):
            if sq[(n-i**2)-j**2]: # 제곱수를 한번 더 뺀 나머지가 제곱수일 경우
                mincount=3
print(mincount)

1. 제곱수를 표시할 배열을 만든다.

2. n을 제곱수/나머지로 나눠 n이 제곱수일 경우 1을 출력하고, 나머지도 제곱수일 경우 2를 출력한다.

3. 위의 경우에 모두 해당되지 않는다면, 나머지를 제곱수/나머지로 다시 나눠 나머지가 제곱수인 경우 3을 출력하고 반복문을 계속 진행하여 최솟값을 찾는다.

4. 조건문에 한번도 걸리지 않았다면 최솟값은 4가 출력된다.