Swift)BOJ - 1699 제곱수의 합(DP)

안녕하세요. 후르륵짭짭 입니다.

www.acmicpc.net/problem/1699

1699번: 제곱수의 합

이 문제를 풀었는데,,, 시간초과 부분을 어떻게 해결하면 좋을까 많은 고민을 했습니다.

DP 문제이기 때문에,, 현재 index에서 절반 까지 확인 하고 가장 작은 것을 찾는 방법으로 짰는데,,, 시간초과,,,

예를들어 )

12 = list[11] + list[1] = list[10] + list[2] = list[9] + list[3] = list[8] + list[4] ,,,

이렇게 탐색하는 방법이였는데,,,

import Foundation

let input = Int(readLine()!)!

var cnt : Int = 1

var list : [Int] = [0]

for index in 1...input{
    
    if cnt * cnt == index {
        list.append(1)
        cnt += 1
        continue
    }
    
    var temp = index - 1
    var inputNum = index

    while temp >= (index / 2) {

        inputNum = min(inputNum, list[temp] + list[index - temp])
        temp -= 1
    }
    
    list.append(inputNum)
    
}

print(list[input])

깊은 고민과 질문 게시판을 통해서 더 좋은 방법을 찾았습니다.

하나씩 줄여가면서 탐색하는 것이 아니라

12 = list[11] + 1 = list[8] + 1 = list[3] + 1

이렇게 제곱형식으로 올라가면서 가장 작은 값을 선택하는 방향으로 하면 된다는 겁니다.

let input = Int(readLine()!)!

var cnt : Int = 1

var list : [Int] = [0]

for index in 1...input{
    
    if cnt * cnt == index {
        list.append(1)
        cnt += 1
        continue
    }
    
    var inputNum = index
    var start = 1
    
    while start * start < index {
        inputNum = min(inputNum, list[index - start * start] + 1)
        start += 1
    }
    
    list.append(inputNum)
    
}

print(list[input])

 

아,,,, 오랜만에 알고리즘 문제로 이것을 풀었는데,,, 확실히 생각의 틀을 넓힐 필요가 있는 것 같습니다.

속도를 확실히 줄이는 방법은 제곱방식이 있다는거!