문제설명

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

접근

그 항의 최소개수를 구하는
어떠한 수를 제곱수의 합으로 표현할 때, 그 수에서 그 수보다 크지 않은 제곱수를 한 번 뺏을 때의 수도 최소항으로 구성됨 => 작은 부분의 해가 큰 부분의 해에도 계속해서 영향을 주므로 다이나믹 프로그래밍의 보텀업 방식으로 해결 가능함

점화식
d[n] = min(d[n - j] + 1)
j = n 보다 크지 않은 제곱수

다른 사람의 풀이

# 출처 - https://pacific-ocean.tistory.com/205
## 보텀업 방식
n = int(input())
# 결과 저장용 리스트
dp = [0 for i in range(n + 1)]
# 제곱수 리스트
square = [i * i for i in range(1, 317)]
for i in range(1, n + 1):
	# dp의 값으로 들어갈 수 있는 후보군 리스트
    s = []
    for j in square:
    	# 제곱수보다 작지 않은 경우일때까지만 후보군 리스트에 저장 
        if j > i:
            break
        s.append(dp[i - j])
    # 점화식에 따른 결과를 dp에 저장
    dp[i] = min(s) + 1
print(dp[n])

배운점

• 값이 고정된 리스트는 파이썬다운 방식으로 리스트표현식으로 저장할 수 있다
• 다이나믹 프로그래밍의 보텀업 방식으로 풀이시 예시를 몇개 적어보고 점화식을 추출한다