[백준/Swift] 1699번: 제곱수의 합

 

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 

//(1)1 -> 1^2
//(2)2 -> 1^2 + 1^2
//(3)3 -> 1^2 + 1^2 + 1^2
//(1)4 -> 2^2
//(2)5 -> 1^2 + 2^2
//(3)6 -> 1^2 + 1^2 + 2^2
//(4)7 -> 1^2 + 1^2 + 1^2 + 2^2
//(2)8 -> 2^2 + 2^2
//(1)9 -> 3^2
//(2)10 -> 1^2 + 3^2
//(3)11 -> 1^2 + 1^2 + 3^2
//(4)12 -> 1^2 + 1^2 + 1^2 + 3^2
//(2)13 -> 2^2 + 3^2
//(3)14 -> 1^2 + 2^2 + 3^2
//(4)15 -> 1^2 + 1^2 + 2^2 + 3^2
//(5)16 -> 1^2 + 1^2 + 1^2 + 2^2 + 3^2
//(3)27 -> 2^2 + 2^2 + 3^2

여기서 보면 제곱수들이 나름 규칙을 가지고 있는 것을 알 수 있다.

우선, 현재 자신(i) 보다 작은 값의 제곱이 i보다 크면 안 된다. 나보다 큰 값과 어떤 값의 합으로 나를 나타낼 순 없으니까!

그래서 1부터 i까지의 값 중 값의 제곱(j*j)이 i보다 작은 애들만 보면서 진행해야 한다.

내 앞 수(j)의 제곱을 빼면서 그 값(dp[i-j*j])에 +1 한 값이 dp[i]의 값이 되는데, 이를 계속 비교하면서 가장 작은 개수를 넣어주면 된다.

 

import Foundation

/*
 N은 그보다 작거나 같은 제곱수의 합으로 나타낼 수 있다.
 제곱수 항의 최소 개수를 출력하자.
 */

//input
let n = Int(readLine()!)!
var dp = [Int](repeating: 0, count: n + 1)
for i in 1...n {
    dp[i] = i
    var j = 1
    while j * j <= i { //제곱수 체크. 나보다 큰 값이라면 사용하지 않음!
        dp[i] = min(dp[i], dp[i-j*j] + 1)
        j += 1
    }
}
print(dp[n])

제곱을 생각하는데 있어서 시간이 좀 걸렸다...

이런 유형이 있다는 것을 기억해야겠다!