1. 문제 설명

제곱수의 합

2. 문제 분석

특정 수를 제곱했을 때 바로 그 수가 나온다면 (즉 2-4, 3-9...) 제곱수로 표현 가능한 개수는 1개로 최소다. 그렇지 않다면 현재 수 i에서 i보다 작은 게 보장된 수들의 제곱수를 뺀 dp에 기록된 값 + 1 중 최솟값이 가장 적은 개수로 표현된 제곱수의 개수다.

3. 나의 풀이

import Foundation

let N = Int(String(readLine()!))!

func getNumber(num: Int) -> Int {
    var dp = Array(repeating: 0, count: num+1)
    if num <= 3 {
        return num
    } else {
        var powered = [Int]()
        powered.append(0)
        let sqrtLimit = Int(sqrt(Double(num)))
        for i in 1..<(sqrtLimit+1) {
            powered.append(i * i)
        }
        // powered[index] = index * index
        dp[1] = 1
        dp[2] = 2
        dp[3] = 3
        var cursor = 2
        // cursor는 제곱했을 때 현재 수보다 작은 수 중 가장 큰 수
        for i in 4..<(num+1) {
            if (cursor + 1) * (cursor + 1) == i {
                cursor += 1
            }
            if cursor * cursor == i {
                dp[i] = 1
                // 현재 인덱스 자체가 제곱수일 때 체크
            } else {
                var curMin = Int.max
                for j in 1..<(cursor + 1) {
                    curMin = min(1 + dp[i - powered[j]], curMin)
                }
                dp[i] = curMin
                // j(cursor...1)까지 제곱수를 현재 수에서 뺀 수 인덱싱
                // -> 1 + dp[x] 개를 통해 현재 수 i를 표현 가능 보장
                // i를 표현 가능한 수 중 최소 개수 dp에 기록하기
            }
        }
        return dp[num]
    }
}

let answer = getNumber(num: N)
print(answer)