문제
https://www.acmicpc.net/problem/17626
라그랑주는 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과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.
풀이
여러가지 접근법이 있지만 순수하게 python으로 문제를 풀고 싶다면 제일 첫 지문을 잘 읽어야 한다. 첫 지문에 보면 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다라고 적혀있다.
그렇다는 말은 답은 1~4안에 나올 수 있다는 말이다. 그럼 조건을 잘 걸어서 1 , 2 , 3 , 4 중에서 답을 찍어주면된다. (이걸 몰라서 몇시간을 헤맸다ㅠㅠ)
1트
- 처음에는 탐욕(Greedy)법을 시도했다.
- 재귀 함수를 사용해 제곱수인경우와 제곱수가 아닌 경우로 나눠 탐색했는데 당연하게도 시간초과가 나왔고 나중에 확인했지만 답도 틀렸다.
def four_squares(n):
if n == 1:
return 1
sqrt = n**0.5
if sqrt.is_integer():
return 1
return four_squares(n-int(sqrt)**2)+12트
- 다음으로는 재귀만을 사용해 가능한 제곱수 중에서 최소값을 찾는 방식을 시도했다.
- 결과는 당연하게도 시간초과! 그리디보다 로직이 더 추가됐으니 당연한 결과였다.
def four_squares(n):
sqrt = n ** 0.5
if sqrt.is_integer():
return 1
tmp = []
for i in range(int(sqrt), 0, -1):
tmp.append(four_squares(n-(i**2))+1)
tmp.sort()
return tmp[0]3트
- 이쯤되니 당연히 DP로 풀어야할 것이라는 감이 와서 DP를 시도했다.
- 하지만 여전히 결과는 시간초과! 아무래도
PYPY를 사용하지 않으면 안되나?
def four_squares(n):
DP[1] = 1
for i in range(2, n + 1):
for j in range(1, int(i ** 0.5) + 1):
DP[i] = min(DP[i], DP[i - j * j] + 1)
return DP[n]4트
- 결국 로직은 좀 더 가다듬었지만 시간초과를 극복하지 못하고
PYPY를 사용해 통과했다.
- 다른 분들의 풀이를 보고 문제를 다시 보니 문제에 "Four Squares"라고 아주 친절하게 나와있다. 😂
- 이 코드에는
1과2까지만 반환하게 했지만3까지 고려하는 로직을 추가하면 DP까지 쓰지 않더라도 충분히 풀어낼 수 있는 것 같다.
답
from sys import stdin, setrecursionlimit
input = stdin.readline
# PyPy3 : 통과
def four_squares(n):
if (n ** 0.5).is_integer():
return 1
for i in range(2, n + 1):
_min = 1e9
if n > i * i and ((n - i * i) ** 0.5).is_integer():
return 2
for j in range(1, int(i ** 0.5) + 1):
_min = min(_min, DP[i - j * j] + 1)
DP.append(_min)
return DP[n]
if __name__ == "__main__":
N = int(input())
DP = [0, 1]
res = four_squares(N)
print(res)
1등의 풀이
- eric9709님의 풀이를 참고해 DP없이도 풀어봤다. (
is_integer함수를 제외하면 똑같다고 보면 된다.)
1,2,3,4일때 각각 제곱수의 범위안에서 반복문을 돌며 확인하는 방식이다.
def four_squares(n):
if (n ** 0.5).is_integer():
return 1
for i in range(1, int(n ** 0.5) + 1):
if n < i ** 2:
break
if ((n - i ** 2) ** 0.5).is_integer():
return 2
for i in range(1, int(n**0.5) + 1):
if n < i ** 2:
break
for j in range(1, int((n - i ** 2) ** 0.5) + 1):
if n < i ** 2 + j ** 2:
break
if ((n - i ** 2 - j ** 2) ** 0.5).is_integer():
return 3
return 4
Uploaded by Notion2Tistory v1.1.0