17626번: Four Squares
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1
www.acmicpc.net
문제
라그랑주는 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과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.
코드
- PyPy3로만 통과 가능한 코드
import math
n = int(input())
dp = [5] * 50001
dp[0] = 0
for i in range(1, n+1):
for j in range(int(math.sqrt(i)), 0, -1):
if dp[i] == 1:
break
dp[i] = min(dp[i], (dp[i-j**2] + 1))
print(dp[n])
- 브루트포스 (Python3로도 통과)
import math
n = int(input())
dp = [-1] * 50001
# n이 제곱수일 때
if int(math.sqrt(n)) == math.sqrt(n):
print(1)
exit()
# n이 2개의 제곱수의 합일 때
# 즉, sqrt(n - i**2)가 정수일 때
for i in range(int(math.sqrt(n)), 0, -1):
if int(math.sqrt(n-i**2)) == math.sqrt(n-i**2):
print(2)
exit()
# n이 3개의 제곱수의 합일 때
# 즉 sqrt(n - i**2 - j**2)가 정수일 때
for i in range(int(math.sqrt(n)), 0, -1):
for j in range(int(math.sqrt(n - i**2)), 0, -1):
if int(math.sqrt(n - i**2 - j**2)) == math.sqrt(n - i**2 - j**2):
print(3)
exit()
print(4)
- $\sqrt{n^2}$이 정수이면 n이 제곱수
- $\sqrt {n-i^2}$이 정수이면 n이 2개의 제곱수의 합
- $\sqrt{n-i^2-j^2}$이 정수이면 n이 3개의 제곱수의 합
- 다 아니면 4개의 제곱수의 합 ($\because$ 문제에서 모든 수는 4개 이하의 제곱수의 합으로 나타낼 수 있다고 함)
- DP로 파이썬 통과
import math
n = int(input())
dp = [5] * 50001
for i in range(1, int(math.sqrt(n)) + 1): # 제곱수들은 1로 초기화
dp[i**2] = 1
def lag(n):
if dp[n] == 1:
return 1
# n - i**2가 제곱수인 경우
for i in range(1, int(math.sqrt(n)) + 1):
if dp[n-i**2] == 1:
return 2
# n - i**2 - j**2가 제곱수인 경우
for i in range(1, int(math.sqrt(n)) + 1):
for j in range(1, int(math.sqrt(n-i**2)) + 1):
if dp[n-i**2-j**2] == 1:
return 3
return 4
print(lag(n))
- dp 배열은 몇 개의 제곱수의 합으로 되어 있는지 저장하는 배열
- 제곱수들은 미리 dp 배열의 값을 1로 초기화시켜줌
- lag() 함수
- dp[n] == 1 인 경우 즉, n이 제곱수인 경우 1을 리턴
- dp[n-i**2] == 1 인 경우 즉, $n-i^2$가 제곱수인 경우 제곱수 2개의 합이므로 2를 리턴
- dp[n-i**2-j**2] == 1 인 경우 즉, $n-i^2-j^2$가 제곱수인 경우 제곱수 3개의 합이므로 3을 리턴
- 다 아니면 4개의 제곱수의 합인 것이므로 4를 리턴
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 9095번 1, 2, 3 더하기 (0) | 2023.02.10 |
---|---|
[Python/파이썬] 백준 1463번 1로 만들기 (0) | 2023.02.10 |
[Python/파이썬] 백준 2839번 설탕 배달 (0) | 2023.02.09 |
[Python/파이썬] 백준 1010번 다리 놓기 (0) | 2023.02.09 |
[Python/파이썬] 백준 10870번 피보나치 수 5 (0) | 2023.02.09 |