BOJ-1699 제곱수의 합 Swift

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 $$11= 3^{2}+1^{2}+1^{2}$$ (3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 $$11= 2^{2}+2^{2}+1^{2}+1^{2}+1^{2}$$(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

내가 푼 풀이

- 처음에는 단순히 자연수 N과 크기가 비슷하고 작은 제곱수부터 빼면서 카운트를 했는데 실패가 떴다.

$$43 = 6^{2}+7 = 6^{2}+2^{2}+1^{2}+1^{2}+1^{2}$$

$$43 = 5^{2}+18 = 5^{2}+3^{2}+3^{2}$$

- 43은 위와 같이 N보다 작은 값중에 가장 큰 값을 빼가며 카운트하는 것은 정답이 아니게 될 수 있다.

- 가장 큰값을 빼가는 그리디방식은 이문제와 맞지 않다.

- dp[n] = 자연수 n의 제곱수의 항의 최소 개수라 정의하자.

- 제곱수 항의 개수가 최대가 되는 방법은 모든 제곱수가 1의 제곱이 되는 것이다.

- 초기값은 dp[n] = arr[n]이다.

- 1부터 n의 제곱근까지 자연수 n을 빼가며, 항의 최소개수를 입력한다.

- dp[n] = min(dp[n], dp[n - idx * idx] + 1) ( idx는 1부터 n의 제곱근까지의 범위)

 

이를 코드로 구현해 보자

 

import Foundation

var num = Int(readLine()!)!
var dp = [0] + Array(1...num)

// dp 입력
// dp[n]의 제곱수항의 갯수 최댓값은 모든 제곱수가 1인것
// n이 제곱수라면 dp[0] + 1 인 값이 최솟값이 되는것이다.
for i in 1...num {
    var idx = 1
    while idx * idx <= i {
        dp[i] = min(dp[i], dp[i - idx * idx] + 1)
        idx += 1
    }
}
print(dp[num])