[백준] 1699(파이썬) 제곱수의 합

1699번 제곱수의 합

DP문제이다.
이번 문제는 제곱수의 합으로 수를 표현하되, 가장 적은 갯수의 수들로 구성해야 한다.
예로 $11=3^2+1^2+1^2$ 처럼 3개의 수를 이용해서 표현할 수 있고, $11=2^2+2^2+1^2+1^2+1^2$ 과 같이 5개의 수를 이용해서 표현할 수도 있다.

DP문제는 점화식을 찾는게 핵심이므로, 규칙을 찾기위해서 1부터 한번 쭉 나열해 보았다.

1=1^2						1개
2=1^2 + 1^2					2개
3=1^2 + 1^2 + 1^2			3개
4=2^2						1개
5=2^2 + 1^2					2개
6=2^2 + 1^2 + 1^2			3개
7=2^2 + 1^2 + 1^2 + 1^2		4개
8=2^2+2^2					2개
9=3^2						1개
.
.
.

처음에는 도저히 규칙이 보이지 않아서, 항끼리 더해보고 곱해보고 등등 다해봤다.

다시 천천히 생각해보자.

dp[n]은 무엇을 표현하는가?

• 제곱들의 합으로 n이 표현되는, 제곱 수의 최소 갯수

이말은 즉, n에서 특정 제곱수를 뺀다는 것은 뺀 그 수도 제곱들의 합으로 이루어진 수라는 것이다.
(예 n=10일때, $10=3^2+1^2$ 으로 이루어져 있다. 이때 $1^2$을 빼면 $3^2$ 이 된다. 즉, dp[9]의 값이 되는 것이다.
고로 10은 dp[9]의 값에+1 이 되는 형식인것이다.)
이렇게 특정 제곱수를 빼주는 과정을 for문을 통해 돌리고, 매번 나오는 갯수의 값을 min을 이용하여 비교하면 된다.

이것을 점화식으로 풀어보면, dp[i-j**2]+1이 dp[i]의 값이 되는 것이다.

따라서 코드로 짜보면

#1699

import sys
input=sys.stdin.readline

n=int(input())

dp=[0]*100001

for i in range(1, n+1):
	#제곱수로 이루어진 숫자일때
    if int(i**0.5)==i**0.5:
        dp[i]=1
    else:
        min_value=1e9
        1부터 i의 제곱근까지만 해야 dp[-1]와 같은 out of index를 피한다.
        for j in range(1, int(i**0.5)+1):
            min_value=min(min_value, dp[i-j**2])
        dp[i]=min_value+1

print(dp[n])

dp는 진짜 생각이 안나면 죽어도 안 나는것 같다. 연습을 통해 갈고 닦자.