본인의 부족함을 많이 느끼게 된 문제였다. 쉬운 문제를 풀어야겠다고 생각하고 풀었는데 다소 고전했다.
DP에 대해서 잘 알고 있다고 생각했는데, 예전부터 느꼈듯이 점화식을 세우는 것에 대한 수학적 사고가 아직 많이 부족하다.
결국에 블로그를 참고해서 문제를 풀게 되었다.
문제 이해 및 적용하기
이 문제는 입력된 수를 제곱수의 합으로 나타낼 수 있다. 그러면 DP에 저장해야하는데 어떤 것을 저장해야할까?
당연히 각각의 제곱수 합 항의 최소개수 이다.
그러면 각각의 제곱수 합 항의 최소개수는 어떻게 구하는 것일까?
여기서 본인은 min((i) + (input number-i))로 점화식을 처음에 세웠었다.
하지만, __가능한 모든 제곱수를 뺀 수의 DP 중에 최소값__을 구해야한다.
예를 들어 21이면, min(dp[21-11], dp[21-22], dp[21-33],dp[21-44]) + 1 을 해주어야 할 것이다.
여기서 +1을 해주는 이유는 -i*i의 경우도 합이 1로 들어가니까 고려해주어야 하기 때문이다.
여기서 한번 더 경우의 수를 뺄 수가 있는데, dp[21-11]는 결국에 dp[11]을 전부 더하는 것을 의미함으로 제거해줘도 무방하다.
이 점화식만 알면 dp개념을 하드코딩하는 것이 없기 때문에 쉽게 풀리는 문제이다.
수학적인 사고력을 요하는 문제였고, 본인은 그것에 취약하다는걸 또한번 되새기는 시간이었다.
또한, Pypy3로 해야 통과가 가능하고, 가끔 Python3로 통과되는 코드도 보였는데, 불필요한 순회를 if문으로 많은 경우의 수를 제거해주었을때 오랜시간이 걸려 채점이 되는 것을 확인하였다.
주의할 점
- +1을 해주는 이유는 -i*i의 경우도 합이 1로 들어가니까 고려해주어야
- 한번 더 경우의 수를 뺄 수가 있는데, dp[21-11]는 결국에 dp[11]을 전부 더하는 것을 의미함으로 제거해줘도 무방
- Pypy3로 돌려야 함.
전체코드
import sys
input = sys.stdin.readline
n = int(input())
dp = [100000 for i in range(100001)]
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3
i = 1
while(i**2 < n+1):
dp[i**2] = 1
i+=1
for i in range(2,n+1):
j = 2
while(j*j <= i):
dp[i] = min(dp[i],dp[i-j*j]+1)
j+=1
print(dp[n])