[코딩 테스트 연습(파이썬/Python)] 백준 1699번 _ 제곱수의 합

https://www.acmicpc.net/problem/1699

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)

[출력]

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

[아이디어]

i의 구하는 값은 i보다 작은 제곱수로부터 가장 적은 횟수로 i의 도달할 수 있는 횟수다.

7의 경우 2^2 + 3,

11의 경우 3^2 +2,

12의 경우 2^2 + 8 

과 같은 식이다. 늘 가장 큰 제곱수로부터 출발해 i에 도달하는 것이 아니라는 것을 12와 같은 예시에서 확인할 수 있어야 한다.

n = int(input())
a = [1,2,3] + [0]*(n-3)
if n <=3: print(a[n-1])
else:
    for i in range(3,n):
        k = int((i+1)**(0.5))
        if k == (i+1)**(0.5): a[i] =1
        else:            
            for j in range(1, k+1):
                tmp = a[j**2-1] + a[i-j**2]
                if a[i] ==0:
                    a[i] = tmp
                elif a[i] > tmp:
                    a[i] = tmp
    print(a[-1])

위 코드는 Python3로 제출하면 시간 초과가 나고, Pypy3로 제출해야 통과된다. 중간의 a[j**2-1]은 항상 1이므로 1로 대체될 수 있다.

n=int(input())
x=[0]
for i in range(1,n+1):
	x.append(1+min([x[i-(k+1)**2] for k in range(int(i**.5))]))
print(x[-1])

같은 논리이긴 하지만, 위처럼 1부터 차례로 append해나가는 방법도 있다. 시간 복잡도 면에서 같거나 오히려 내 것이 나아보이는데 내 코드는 왜 시간 초과가 나는지 잘 모르겠다..