[swift] 백준 - 17626번: Four Squares

17626번: Four Squares

---

나의 풀이

let n = Int(readLine()!)!
var dp = [Int](repeating: 5, count: n+1)
dp[0] = 0
for i in 1...n {
    var j = 1
    while j * j <= i {
        dp[i] = min(dp[i], dp[i - j * j] + 1)
        j += 1
    }
}
print(dp[n])

풀이 키워드

DP
브루트포스 알고리즘
dp배열에 제곱수의 개수를 저장해가며 답을 구한다.
dp[i - j * j] + 1이 문제의 핵심 키워드

예시)

입력: 10
10보다 작은 제곱수를 구한다
j = 1 일 때 1*1 == 1
dp[10 - 1] == dp[9]일 때 의 제곱수의 개수에서 +1을 해 dp[10]에 넣는다.
+1을 하는 이유는 1의 제곱을 더해줘 제곱수가 하나 늘기 때문이다.
j = 2 일 때 2*2 == 4
dp[10 - 4] == dp [6]일 때 의 제곱수의 개수 +1이 현재 dp[10]과 비교해 작은 수를 dp[10]에 넣는다.
j = 3 일 때 3*3 == 9
dp[10 - 9] == dp [1]일 때 의 제곱수의 개수 +1이 현재 dp[10]과 비교해 작은 수를 dp[10]에 넣는다.

출력: 2

---