백준[ 1699 | Python ] 제곱수의 합

문제

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

풀이

dp테이블에 n까지의 수를 미리 입력한다.(n까지의 모든 수의 최대항의 합. 예로 5는 (1^2)*5이다.)
그 후 이중for문으로 탐색을 하는데, 탐색하는 수의 제곱이 현재값보다 높으면 더이상 원하는 값을 찾을 수 없으므로 반복문을 탈출한다.
(모든 수를 탐색, 판단하는 경우를 방지한다.)

그 외의 경우는 현재의 제곱수 항들과 현재수에서 탐색하고 있는 j의 제곱수를 빼준 값에 1을 더한 값 중 작은 값을 dp테이블에 넣어준다.
이때 j의 제곱수를 빼준 값에 1을 더해주는 이유는
i가 5인 경우일 때 생각해보면, 5는 2^2+1^2로 현재값 5에서 4(1개의 항,현재값 i보다 작은 가장 큰 제곱 수)를 빼준 것에 대한 보상이기 때문이다.

결국 dp[i-j*2]라는 문장은 현재값에서 가장 큰 값을 빼줬을 때 남는 값의 항 수를 dp테이블에서 참조한 것이 되는 것이고,
현재값의 항 수 5(1^2) 보다 2^2의 항 수 + dp[1](1의 제곱 수)가 더 작은 수가 되기 때문에 최소항의 합을 구할 수 있다.

n = int(input())
dp = [0]*(n+1)
for i in range(1,n+1):
    dp[i] = i
    for j in range(1,i):
        if j**2 > i:
            break
        dp[i] = min(dp[i], dp[i-j**2]+1)
print(dp[n])

생각 & 정리

개인적으로 다른 DP문제보다 가장 이해하기 힘들고 혼자서는 구현하기 힘든 문제였다.
먼저 제곱수항의 합이 다른 수의 제곱근이 되면 그 수가 초기화 된다는 것은 알고 있었는데,
이를 어떻게 구현할지가 정말 곤혹스러웠다.
점화식을 통해 DP를 구현하는 것은 그나마 이해가 잘 되는 편인데, 결과값 자체를 인덱스로 사용하는 것이
아직도 어색하고 어떻게 사용해야할지 잘 감이 안오는 것 같다.
전에도 느꼈듯이, 다른 분류들 보다 더 많이 접해보면 익숙해질 것이라고 믿는다.