BOJ 1699: 제곱수의 합

오늘도 다이내믹 프로그래밍 문제를 풀고 있다. 

풀다 보니까, 이것도 다이내믹 프로그래밍이야? 라고 생각 하게 만드는 문제들도 정말 많다.

이 문제가 바로 이와 같은 경우다.

---

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

1699번: 제곱수의 합

 

---

처음에 풀었던 내 잘못된 풀이이다.

n이라는 수가 주어지고, 그 수보다 작은 제곱수를 빼면 된다고 생각을 했었다.

from math import *
n=int(input())
result=0
while n>0:
  root=int(floor(sqrt(n)))
  n-=root**2
  result+=1
print(result)

그러나 이 방법으로 풀면, 20000같은 수가 제시되었을 때, 20000보다 작은 제곱수를 빼야 하지만, 그렇게 빼는 것 보다 100의 제곱인 10000을 두번 더하는 것이 더 빠르다.

결국 오답이다.

---

그렇기에 고민 끝에 다른 블로그를 참고했다.

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])

단순하지만, 강력하다.

반복문을 돌면서, 주어진 수 n보다 작은 모든 제곱수에 대해서 빠진 수를 돌면서, dp를 업데이트한다.

 

예를 들자.

13이라면, 

원래 dp[4]=4였을 것이다.

그러나 i가 4일때 j=2면, 

dp[4]=dp[4-2*2]+1에 딱 맞아 떨어질 것이다.

dp[4]=1+1=2가 들어간다.

이런식으로 모든 index의 최솟값을 구해본다..!

---

아직 다이내믹 프로그래밍 문제를 식별하는 것도, 기본 점화식을 만들어 내는 것도 참 어렵다.

그렇지만, 더욱 열심히 화이팅!