728x90
문제 설명
자연수 ( n )이 주어질 때, ( n )을 최소 개수의 제곱수 합으로 표현하는 방법을 찾는 프로그램을 작성하는 문제이다. 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 예를 들어, 26은 ( 5^2 + 1^2 )로 표현할 수 있고, ( 4^2 + 3^2 + 1^2 )로도 표현할 수 있다. 이 문제에서는 ( n )을 최소 개수의 제곱수 합으로 표현할 때 그 최소 개수를 구해야 한다.
풀이 설명
이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있다.
def min_squares(n):
# dp[i]는 i를 최소 개수의 제곱수 합으로 표현하는 방법의 개수를 저장
dp = [float('inf')] * (n + 1)
dp[0] = 0 # 0은 제곱수의 합으로 표현할 필요가 없으므로 0개
# 1부터 n까지의 각 수에 대해 최소 제곱수 합의 개수를 계산
for i in range(1, n + 1):
j = 1
while j * j <= i:
dp[i] = min(dp[i], dp[i - j * j] + 1)
j += 1
return dp[n]
# 입력을 받아 결과 출력
n = int(input())
print(min_squares(n))
코드 설명
- 초기화:
dp배열을inf로 초기화한다.dp[i]는 ( i )를 제곱수 합으로 표현할 때 최소 개수를 저장한다.dp[0]은 0으로 설정한다. 0은 제곱수 합이 필요 없으므로 0개이다.
- 동적 계획법 적용:
i를 1부터 ( n )까지 반복하며, 각 숫자i를 제곱수 합으로 표현할 때의 최소 개수를 계산한다.j를 1부터 시작하여j^2가i보다 작거나 같은 동안 반복한다.dp[i]는dp[i - j^2] + 1중 최소값으로 갱신된다. 여기서dp[i - j^2]는i에서j^2를 뺀 수를 제곱수 합으로 표현한 최소 개수에 1을 더한 값이다.
- 결과 반환:
최종적으로 dp[n]이 ( n )을 제곱수 합으로 표현할 때 최소 개수를 저장하고 있다.
이 알고리즘은 ( n )이 최대 50,000까지 주어질 수 있으므로 효율적인 동적 계획법을 사용하여 문제를 해결한다.
dp 배열을 이용한 풀이로 시간 복잡도는 ( O(n * sqrt{n}) )이다. 이는 제곱수를 체크하는 이중 루프에서 발생하는 시간 복잡도이다.
++ Python 브루트포스 풀이
728x90
