[백준/Swift] 18429번: 근손실

 

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

18429번: 근손실

 

 

백트래킹은 DFS와 달리 불필요한 탐색은 하지 않는다.

그래서 앞의 키트에서 중량 500을 넘기지 못하면 뒷부분 키트도 사용해보지 않고 패스하도록 했다.

(cnt == n 조건까지 들어가지 않고 패스하기)

500을 넘는 애들만 재귀호출 진행.

 

import Foundation

//input
let nk = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (n, k) = (nk[0], nk[1])
var check = [Bool](repeating: false, count: 9)
var arr = readLine()!.split(separator: " ").map{ Int(String($0))! }
var answer = 0

func bt(_ cnt: Int, _ weight: Int) {
    if cnt == n {
        answer += 1
        return
    }
    for i in 0..<n {
        if !check[i] {
            if weight - k + arr[i] < 500 { continue }
            check[i] = true
            bt(cnt+1, weight - k + arr[i])
            check[i] = false
        }
    }
}
bt(0, 500)
print(answer)