Four Squares
출처 : 백준 #17626
| 시간 제한 | 메모리 제한 |
|---|---|
| 0.5초 | 512MB |
문제
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.
자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.
입력
입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.
출력
출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.
입출력 예시
예제 입력 1
25
예제 출력 1
1
예제 입력 2
26
예제 출력 2
2
예제 입력 3
11339
예제 출력 3
3
예제 입력 4
34567
예제 출력 4
4
풀이
생각 및 풀이 설명
-
DP 문제로 접근하였다.
-
base case로 n보다 같거나 작은 수들 중 제곱으로 표현할 수 있는 수는
dp[i] = 1로 정했다. -
for 문을 돌면서 제곱으로 나타낼 수 있는 수가 아니라면(=
dp[i] != 1), 현재의 인덱스에서 제곱으로 나타낼 수 있는 수를 빼준 값을 인덱스로 하여, 인덱스에 해당하는 수들을 비교한 후 가장 작은 값에 1을 더하여 준다.- 1을 더하는 이유 : 예를들어 8을 나타내려고 할 때 8보다 작은, 제곱으로 나타낼 수 있는 수는 1과 4가 있다.
- 그럼 8-1, 8-4 즉, 7과 4에 해당하는 값을 찾아야 한다.
- 이때
dp[7]= 4,dp[4]= 1이다. - 4로부터 4만큼 더해주면 되므로, 1을 추가해주는 것이다.
-
이 문제는 내가 짠 코드로는 python3 기준 시간초과가 발생했다.
-
그러나 pypy로 했더니 통과했다. (가끔은 이렇게 pypy로 통과하는 경우가 있으니 알아두자.)
-
python3로 풀 수 있는 코드는 1, 2, 3, 4로 경우를 나누어 푼 코드이다.(DP 이용 X)
- 4이하의 자연수로 표현할 수 있기 때문이다.
python code(pypy3에서 정답, python3 시간초과)
# 백준 17626번 Four Squares
from sys import stdin
input = stdin.readline
n = int(input())
dp = [0] * (n+1)
i = 1
squareArr = []
while i**2 <= n:
dp[i**2] = 1
squareArr.append(i**2)
i += 1
for j in range(1, n+1):
if dp[j] != 1:
temp = 4
for x in squareArr:
if x <= j:
if dp[j-x] <= 3:
if dp[j-x]+1 < temp:
temp = dp[j-x] + 1
else:
break
dp[j] = temp
print(dp[n])python code(python3 정답)
import sys
input = sys.stdin.readline
n=int(input())
def is_square(n):
if n==int(n**0.5)**2:
return True
else:
return False
def is_two(n):
for i in range(int(n**0.5) ,0,-1):
if i**2<n/2:
return False
if is_square(n-i**2):
return True
return False
def is_three(n):
for i in range(int(n**0.5),0,-1):
# print('i2',i)
if is_two(n-i**2):
return True
if i**2<n/2:
return False
return False
if is_square(n): print(1)
elif is_two(n) : print(2)
elif is_three(n) : print(3)
else : print(4)