[백준/Python] 1699 - 제곱수의 합

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

---

풀이
우선은 표를 그려서 규칙을 확인해봤다

	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$1^2$	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$2^2$				1	2	3	4	2	3	4	5	3	4	5
$3^2$									1	2	3	4	2	3

가로는 n을 의미하고 세로는 제곱수들이다. for루프를 돌면서 $1^2$로 n을 표현하는 방법들 중 최소 개수를 기록하고, $2^2$를 포함하여 n을 표현하는 방법들 중 최소 개수를 적어나가다보면, 규칙이 하나 있다

n을 제곱수로 나눈 나머지가 0인 경우에는 그 몫이 최소 개수가 되고, 만약 나누어 지지 않으면 나머지값을 표현하는 최소 개수와 나눈 몫을 더하면 된다
그리고 최종적으로 최소 개수를 구하는 것은 제곱수의 밑을 1씩 증가시켜가면서 현재 최소 개수와 새로운 최소 개수 중 더 작은것으로 갱신해나가면 된다

예를 들어, n이 11이고, $1^2$로 11을 표현하는 최소 개수는 11이다 $1^2$를 11번 더하는 것이다. $2^2$로 11을 표현하는 최소 개수는 5이다. $2^2+2^2+1^2+1^2+1^2$를 수행하면 된다. 이는 11//4 == 2, 11%4 == 3이므로 2+3(3을 표현하는 최소 개수) == 5
11보다 5가 작으므로 n=11일때의 값을 5로 갱신해준다
$3^2$로 11을 표현하는 최소 개수는 같은 방식으로 11//9 == 1, 11%9 == 2 이므로 1+2(2를 표현하는 최소 개수) == 3 이고 기존 값인 5보다 작으므로 3으로 갱신한다

N의 최대값은 100,000이기 때문에 가능한 제곱수의 최대값은 100,000의 제곱근이다
그리고 제곱을 계산할 때 ** 연산자를 사용하는건 굉장히 느리다는 것을 알게 됐다
어차피 제곱을 수행하는 것이므로 그냥 수를 두 번 곱해주면 된다

오랜만에 나름 깔끔하게 잘 풀어서 기분이 좋다 좀 더 연습해서 문제 푸는 시간을 단축하면 좋겠다!

코드

import sys, math

n = int(sys.stdin.readline())

dp = [float("inf")]*(n+1)
dp[0] = 0

for i in range(1, int(math.sqrt(n))+1):
    num = i*i
    for j in range(1, n+1):
        if j%num == 0:
            dp[j] = min(dp[j], j//num)
        else:
            dp[j] = min(dp[j], j//num+dp[j%num])
print(dp[n])