문제보기

문제

라그랑주는 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과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

---

풀이

나는 처음에 무작정 가장 큰 제곱수를 빼주는 식으로 while문을 돌려서 개수를 구하는 방법으로 문제를 풀려고 했었다.

입력이 i일 때

정답을 ans라고 가정했다.

while i:
    a = int(i ** 0.5) ** 2
    i -= a
    ans += 1

그런데 이렇게 하면 정답이 나오지 않는다.
예를 들면
11339 를 입력에 넣어보자.

원래 정답은 3인데 5가 나온다. 최소인 경우를 따로 체크해줘야한다는 뜻이다.

dp를 이용하기

dp를 사용해서 입력 n보다 작은 수들의 최소 제곱수의 개수를 저장해놓아야한다.
최소 제곱수는 다음과 같은 점화식으로 구한다.

for i in range(1, int(n ** 0.5) + 1):
    dp[n] = min(dp[n], dp[i * i] + dp[n - i * i])

자기 자신 (n) 보다 작은 제곱수의 dp값(dp[i*i])과 그 수를 뺀 것의 dp값(dp[n - i*i]) 과 비교해서 더 작은 값으로 갱신해주는 것이다.

정답

n = int(input())

dp = [0] * 50001
dp[1] = 1

for x in range(1, n + 1):
    ans = 0
    i = x
    while i:
        a = int(i ** 0.5) ** 2
        i -= a
        ans += 1
    dp[x] = ans

    for j in range(1, int(x ** 0.5) + 1):
        dp[x] = min(dp[x], dp[j * j] + dp[x - j * j])

print(dp[n])