백준 1699 - 제곱수의 합 - swift

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

1699번: 제곱수의 합

 

dp문제이다. 

 

dp [ i ] = i값을 만들기위한 최소한의 항의개수라고 정의한다. 

 

그래서 1부터 N까지 하나씩 탐색하면서,

1부터 N까지중에서 제곱수로 dp를 갱신해나간다. 

 

처음에는 각각 10만*10만 시간복잡도인줄 알아서 고민했는데,

알고보니, 제곱수까지만 확인하면된다. 

즉 N이 10000까지라면,  제곱수는 1부터 100까지만 확인하면 된다.

10만이라면 약 300까지의 제곱수를 확인하면 되고, 이는 3천만의 시간복잡도이므로 2초안에 충분히 계산가능하다. 

 

let N = Int(readLine()!)!
var dp = Array(repeating: Int.max, 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])