[BOJ] 1699번 - 제곱수의 합

---

문제설명

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

1699번: 제곱수의 합

사고과정

• 점화식을 발견하기가 어려웠다.. 제곱수를 어떻게 해야할지 몰랐다..
• 풀이의 핵심적인 아이디어만 보고 소스코드는 직접 작성해보았다. 다행히 이건 통과했다. 
• 문제풀이의 핵심 아이디어는 DP 테이블에는 입력되는 N을 제곱수 합으로 만들 수 있는 가장 최소항 개수를 넣어준다. 그리고 숫자를 $i$라고 할때, $j$는 $i$보다 작거나 같은 제곱수들이라고 하자. 이 때, DP 테이블의 $i$번째 값을 업데이트 하기 위해서는 DP 테이블의 $i-j$번째 인덱스에 있는 값들을 모두 비교해서 가장 최솟값으로 업데이트 해주는 것이다! 제곱수들을 빼주는 이유는 만약 해당 제곱수를 사용했을 때는 어쩄건 1개의 항을 사용한 셈이다. 그리고 $i$에서 사용한 제곱수를 빼주면 나머지 숫자가 있을 것이다. 그 나머지 숫자를 제곱수의 합으로 구할 수 있는 최소 항 개수는 이미 DP 테이블에 업데이트 되어 있을 것이다. 
• 예를 들어, $i$ = 16이라고 해보자. 그러면 $j$는 16, 9, 4, 1 이 나오게 된다. 예시로 $j$가 16일 때를 보면 우선 16을 제곱수로 하나 사용하면 1개의 항을 사용한 셈이다. 그러면 $i$ 에서 16을 빼게 되면 0이 된다. 0은 0개의 항이 필요하다. 따라서 총 항의 개수는 1개이다. 다른 예시로 $j$가 9일때를 들어보자. 9 제곱수를 하나 사용했으니 1개의 항을 사용한다. 그리고 $i$에서 9를 빼면 5가 남는다. 그러면 DP 테이블의 5번 인덱스로가서 숫자 5를 만들 수 있는 최소 항의 개수를 참조해서 더해준다. 이런식으로 $j$들에 대해서 모두 비교하면서 최솟값을 찾는다.(필자는 점화식 풀이는 다른 블로그를 참고했지만 최솟값을 찾을 때는 그리디 방식을 사용했다)
• 주어진 데이터가 최대 10만이였는데, 시간이 2초로 약 1초에 2천만번을 수행할 수 있는 파이썬이기 때문에, 총 4천만번 연산이 가능하다(PyPy3를 사용하면 더 빠름!) 그런데 아래 코드를 보면 바깥 루프에서 약 100만번을 돌게 된다. 그리고 내부 루프에서 제곱근 만큼 돌기 때문에 만약 내부 루프에서 최악의 100만번의 제곱근을 하게 되면 316정도가 나오게 된다. 그렇다면 100만 곱하기 316을 하게 되면 3천 160만번의 연산이 필요하다. 따라서 시간범위 내에 통과할 수 있게 된다!

풀이(스스로 못 푼 풀이)

import math

n = int(input())
dp = [0] * (n+1)

for i in range(1, n+1):
    min_val = int(1e5)
    for j in range(1, int(math.sqrt(i))+1):
        square = pow(j, 2)
        min_val = min(min_val, dp[i - square] + 1)
    dp[i] = min_val

print(dp[n])