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

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

1699번: 제곱수의 합

 

정말 단순하게도 '제곱수들을 N번째 숫자까지 모두 저장해놓고 큰 수부터 빼면 구해지지 않을까?'라고 생각했다. 

하지만 곧 반례를 찾았고, 이미 위와같은 생각에 사로잡혀 다른 방법이 도저히 떠오르지 않았다.

 

심지어 백준님의 강의로 해설을 듣고 나서도

대체 이것이 어떻게 구현된다는 말인지 아직까지도 이해가 안 되고 있다.......

 

대충 50% 정도의 현 이해력으로 정리를 해보자면,

초기 dp에 저장되는 배열은 1~n까지이며

이중 for문을 돌면서 제곱수가 현재의 수보다 크다면 넘기고

현재의 수보다 제곱수가 작다면, 현재의 수 - 제곱수를 하여 그 값에 대한 dp값을 가져온다.

이때 제곱수를 빼고 난 값의 dp값을 가져왔으므로, +1을 해주어 빼준 제곱수의 경우를 더해준다. 

 

이렇게 for문을 다 돌고 나면, 

dp배열의 n번째 수, 즉 입력받은 수의 결과가 저장되므로 dp[n]을 출력해주면 정답!

 

n = int(input())

dp = [ i for i in range(n+1)]

for i in range(1, n+1):
    for j in range(1, i):
        if j*j > i:
            break
        if dp[i] > dp[i-j*j] + 1:
            dp[i] = dp[i-j*j] + 1

print(dp[n])

 

잘 이해가 안돼서 디버깅을 계속해보면서 값의 변화를 관찰했다.

작은 문제부터 풀어나간다는 생각으로 DP문제를 풀어야 하는데... 많이 부족하다는 것을 느낀다.