[Swift][Bruteforce] 백준 14225 (부분수열의 합)

요구능력 : 백트래킹

 

코드설명 : 

 

이 문제는 이 전에 풀었던 부분수열의합(1182번)과 비슷한 느낌의 문제이다.

수열의 경우의수를 백트래킹으로 구하는 부분까지는 같다.

 

이 문제에서의 핵심

1. 백트래킹

2. 시간초과 안나고 없는수를 어떻게 찾을것이냐..

 

처음에는 배열함수써서 인덱스찾고 찾은 인덱스로 지우고.. 뭐 별짓을 다하다가 시간초과가 계속났었다.

시간복잡도에 대해 공부좀해야겠다...

 

내가 해결한방법은 백트래킹으로 부분수열의 합을 구한다음에 나온 합에대한 부분을 true처리해서

for문을 나올 수 있는 최대합의 경우의수까지 돌리면서 false가 맨 처음 나오면 그게 가장 작은수!라고 풀이를 한것이다. 

 

후기 : 어렵지는 않은 문제인데 결과값범위를 잘못잡아서 헤맸다..

let n = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var visited = Array(repeating: false, count: 21)
var sum = 0
var result = Array(repeating: false, count: 2000001)

func dfs(_ depth: Int, _ start: Int){
    if depth >= 1{
        result[sum] = true
    }

    for i in start..<n{
        if !visited[i]{
            visited[i] = true
            sum += arr[i]
            dfs(depth + 1, i)
            visited[i] = false
            sum -= arr[i]
        }
    }
}
dfs(0, 0)

for i in 1...2000000{
    if result[i] == false{
        print(i)
        break
    }
}