[Algorithm] 제곱수의 합

제곱수의 합 문제 풀이

제곱수의 합 - 백준 알고리즘 사이트

: 본래 백준 알고리즘에서 이 문제를 푼 것은 아니지만, 거의 똑같은 문제가 있길래 일단 링크를 첨부한다.

: 사실 이문제는 한번에 풀지 못했다. 인터넷에 해설을 양심적으로 약간 흘끗(?) 보고 또 생각을 해보고, 간신히 푼 문제이다. 사실 정석으로는 이 문제는 답을 보고 포기했어야했던 문제다..ㅎ 시간을 너무 끌어서.. ㅎ 하지만 DP문제 유형에 적응하고자 조금 욕심을 부려서 시간을 오래 투자했고, 나름 얻은게 있던 문제였다.

문제 해석

• 주어진 N을 제곱수의 조합으로 만들되, 그 제곱수의 개수를 최소한으로 사용하여 만들라는 문제이다. 그리고 최소한의 제곱수의 개수를 리턴하는 문제다.
• 주어지는 N이 십만이라서 완전탐색법으로 접근하기에는 무리가 있다.

문제 설계

• 사실 이 문제는 처음 내가 접근하던 방법에서 좀만더 나아갔으면 내 스스로, 힌트 없이 풀 수 있던 문제..라고 하기엔 좀 그렇지만 어쨌든 조금 아쉬운 부분이 있다.

• 맨처음 설계한 부분을 말해보면,

  1 = 1^2
  2 = 1^2 + 1^2
  3 = 1^2 + 1^2 + 1^2
  4 = 2^2 
  5 = 2^2 + 1^2 
  6 = 2^2 + 1^2 + 1^2
  7 = 2^2 + 1^2 + 1^2 +1^2 
  8 = 2^2 + 2^2 
  ......
  12 = 2^2 + 2^2 + 2^2 
  13 = 3^2 + 2^2
  14 = 3^2 + 2^2 + 1^2 
  

  : 위와 같이 14정도까지 직접 해보면서 처음 내린 결론은 주어진 N에 루트를 씌워서 제곱근을 구한다음에 예를 들어, 14면 루트 14 = 3.xxx니까 내림해서 3의 제곱을 14에서 빼준다1). 그러면 14-9 = 5 이므로 이전에 가지고 있던(피보나치 수열처럼 처음부터 값을 받아왔다는 전제) 5의 최소한의 제곱수 개수인 2개를 더해서 3^2 + 2^2 + 1^2 이렇게해서 최소 3개라는 결론을 짓는 식으로 문제를 푸려고 했다.

• 그러나, 문제가 있는게, 예를 들어, 12만 봐도 12에 루트를 씌운 값인 3^2으로 시작하면 3^2 + 1^2 + 1^2 + 1^2 이렇게 4개로 이뤄져 2^2으로 이뤄진 것보다 수가 많게된다. 즉, 제곱근을 가지고 N을 만든다고 하더라도 최소 개수가 100% 나오지는 않는다는 것이다.

• 그래서 생각한 부분은 예를 들어, 12면 루트 12인 3이전까지의 자연수의 제곱을 가지고 계산을 해보는 것이다. 완전탐색에서 약간더 효율적인 방법을 쓰는 방향이라고 생각할 수 있는데, 12로 치면 1^2, 2^2, 3^2을 가지고 접근하는 것이다. 그래서 1^2이면 11이 남으니까 다시 11에서 1^2을 빼서.. 똑같은 시행을 하고..

• 왜그랬는지는 모르겠지만, 잘가다가 갑자기 저기서 또다시 완전탐색법을 사용하고 있던 나를 발견하지 못했다.. 이전의 발상처럼 동적계획법을 써서 12를 예로 들면 1^2, 2^2, 3^2을 12에서 뺀 값에서 최소수를 구하려면 이전에 구해놓은 값으로 가져다 쓰면 되는데, 저기서 한번더 재귀적으로 탐색을 하려던 것이다..

  1 = 1^2
  2 = 1^2 + 1^2
  3 = 1^2 + 1^2 + 1^2
  4 = 2^2 
  5 = 2^2 + 1^2 
  6 = 2^2 + 1^2 + 1^2
  7 = 2^2 + 1^2 + 1^2 +1^2 
  8 = 2^2 + 2^2 
  ......
  12 = 2^2 + 2^2 + 2^2 
  13 = 3^2 + 2^2
  14 = 3^2 + 2^2 + 1^2 
  

  : 다시 위로 돌아와서, 그러면 동적계획법의 스텝1인 구하고자 하는 값을 정의해보면 'i를 만들기 위해 필요한 제곱수의 최소 개수'라고 할 수 있겠다. 그 다음, 이를 구하기 위한 식을 만들어보면(점화식),

  T(i) = MIN(i, T(i-x^2)+1) 
  이 때, x는 1 ~ math.floor(루트 i)
  MIN의 첫번째 요소 i는 x가 바뀌면서 최소값을 갱신해나가는 용도
  

• 위와 같이 짜볼 수 있다. 실제로 위를 코드로 구현해보면,
  : 다음과 같이 짤 수 있다. n이 예를 들어 38이라면, 0부터 38까지 1depth for문을 수행하면서, l이라는 리스트에 해당 값을 넣고, 2depth for문에서는 위에서 설계했던대로 루트i까지의 범위의 자연수의 제곱을 i에서 빼주고 거기에 1을 더한 값(1을 더해주는 이유는 제곱을 빼줄 때 결국 제곱수 하나가 추가되는 것이기 때문)과 현재 l에 있는 값인 예를 들어, 5면 5, 10이면 10 15면 15(전부 1로 만들었다는 가정으로 시작함)을 비교해서 최소값을 탐색하도록 한다.

• 위와 같이하면 최악의 경우 10만 * 루트 10만 의 시행을 하기 때문에 대략 삼천백육십만 정도가 최대 시행이되므로 시간복잡도에 걸리지 않는다.

• 이 문제는 점화식이 쉽게 나오지 않는 문제였던 것 같으면서도, 풀고나니까 좀만 더 디테일하게 파고들었으면 됐을 것 같다는 생각이든다.