[leetcode] 279. Perfect Squares

문제 : https://leetcode.com/problems/perfect-squares/

---

정수 n이 입력으로 주어지면 완전제곱수들의 합으로 n을 만들 때 사용되는 완전제곱수들의 최소 개수를 반환하라.

---

DP로 풀 수 있다.

dp[i] = i를 만들 때 사용되는 완전제곱수들의 최소 개수
      = dp[i - j*j] + 1 들 중 최소값 (j*j <= i)

점화식은 위와 같다.

j는 1부터 제곱수가 i보다 크지 않을때까지 1씩 증가시킨다.

j*j는 항상 완전제곱수가 되므로 i - j*j 를 만들 수 있는 최소 완전제곱수들의 개수를 가져와서 거기서 1 (j*j 한개가 추가)을 더한 값 구하면 정답이 된다.

 

시간복잡도는 O(NlogN). 공간복잡도는 O(N).

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/279.%20Perfect%20Squares.cpp